home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 February: Tool Chest / Dev.CD Feb 95 / Dev.CD Feb 95.toast / Tool Chest / Games / Mac Game Developer's Handbook / Graphics / In Search of Optimal Palette < prev    next >
MacBinary  |  1993-03-15  |  605.1 KB  |  [ONLN/HLX2]
open in: MacOS 8.1     |     Win98     |     DOS

browse contents    |     view JSON data     |     view as text


This file was processed as: MacBinary (archive/macBinary).

ConfidenceProgramDetectionMatch TypeSupport
10% dexvert MacBinary (archive/macBinary) fallback Supported
100% file MacBinary II, inited, Sun Mar 14 20:30:23 1993, modified Sun Mar 14 20:30:31 1993, creator 'HLX2', type 'ONLN', 616059 bytes "In Search of Optimal Palette" , at 0x966fb 3411 bytes resource default (weak)
99% file data default
66% TrID SpeedScript document (C64) default (weak)
33% TrID MacBinary 2 default (weak)
100% siegfried fmt/1762 MacBinary (II) default
100% lsar MacBinary default


id metadata
keyvalue
macFileType[ONLN]
macFileCreator[HLX2]


hex view
+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 1c 49 6e 20 53 65 61 | 72 63 68 20 6f 66 20 4f |..In Sea|rch of O|
|00000010| 70 74 69 6d 61 6c 20 50 | 61 6c 65 74 74 65 00 00 |ptimal P|alette..|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 4f 4e 4c 4e 48 4c 58 | 32 01 00 00 00 00 00 00 |.ONLNHLX|2.......|
|00000050| 00 00 00 00 09 66 7b 00 | 00 0d 53 a7 c9 8c af a7 |.....f{.|..S.....|
|00000060| c9 8c b7 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 23 d2 00 00 |........|....#...|
|00000080| 49 4e 20 53 45 41 52 43 | 48 20 4f 46 20 54 48 45 |IN SEARC|H OF THE|
|00000090| 20 4f 50 54 49 4d 41 4c | 20 50 41 4c 45 54 54 45 | OPTIMAL| PALETTE|
|000000a0| 0d 44 41 56 45 20 47 4f | 4f 44 20 41 4e 44 20 4b |.DAVE GO|OD AND K|
|000000b0| 4f 4e 53 54 41 4e 54 49 | 4e 20 4f 54 48 4d 45 52 |ONSTANTI|N OTHMER|
|000000c0| 0d 57 68 65 6e 20 79 6f | 75 20 77 61 6e 74 20 74 |.When yo|u want t|
|000000d0| 6f 20 64 69 73 70 6c 61 | 79 20 61 6e 20 69 6d 61 |o displa|y an ima|
|000000e0| 67 65 20 74 68 61 74 20 | 63 6f 6e 74 61 69 6e 73 |ge that |contains|
|000000f0| 20 6d 6f 72 65 20 63 6f | 6c 6f 72 20 69 6e 66 6f | more co|lor info|
|00000100| 72 6d 61 74 69 6f 6e 20 | 74 68 61 6e 20 74 68 65 |rmation |than the|
|00000110| 20 64 69 73 70 6c 61 79 | 20 64 65 76 69 63 65 20 | display| device |
|00000120| 69 73 20 63 61 70 61 62 | 6c 65 20 6f 66 20 72 65 |is capab|le of re|
|00000130| 6e 64 65 72 69 6e 67 2c | 20 68 6f 77 20 64 6f 20 |ndering,| how do |
|00000140| 79 6f 75 20 70 69 63 6b | 20 74 68 65 20 62 65 73 |you pick| the bes|
|00000150| 74 20 63 6f 6c 6f 72 73 | 20 74 6f 20 75 73 65 3f |t colors| to use?|
|00000160| 20 54 68 65 20 50 69 63 | 74 75 72 65 20 55 74 69 | The Pic|ture Uti|
|00000170| 6c 69 74 69 65 73 20 50 | 61 63 6b 61 67 65 2c 20 |lities P|ackage, |
|00000180| 6e 65 77 20 69 6e 20 53 | 79 73 74 65 6d 20 37 2c |new in S|ystem 7,|
|00000190| 20 70 72 6f 76 69 64 65 | 73 20 74 77 6f 20 6d 65 | provide|s two me|
|000001a0| 74 68 6f 64 73 2c 20 77 | 68 69 63 68 20 77 65 20 |thods, w|hich we |
|000001b0| 64 65 73 63 72 69 62 65 | 20 68 65 72 65 2e 20 59 |describe| here. Y|
|000001c0| 6f 75 20 61 6c 73 6f 20 | 68 61 76 65 20 74 68 65 |ou also |have the|
|000001d0| 20 6f 70 74 69 6f 6e 20 | 6f 66 20 64 65 76 65 6c | option |of devel|
|000001e0| 6f 70 69 6e 67 20 79 6f | 75 72 20 6f 77 6e 20 63 |oping yo|ur own c|
|000001f0| 6f 6c 6f 72 20 73 65 6c | 65 63 74 69 6f 6e 20 61 |olor sel|ection a|
|00000200| 6c 67 6f 72 69 74 68 6d | 2e 20 54 68 69 73 20 61 |lgorithm|. This a|
|00000210| 72 74 69 63 6c 65 20 61 | 6e 64 20 74 68 65 20 61 |rticle a|nd the a|
|00000220| 63 63 6f 6d 70 61 6e 79 | 69 6e 67 20 63 6f 64 65 |ccompany|ing code|
|00000230| 20 6f 6e 20 74 68 65 20 | 44 65 76 65 6c 6f 70 65 | on the |Develope|
|00000240| 72 20 43 44 20 53 65 72 | 69 65 73 20 64 69 73 63 |r CD Ser|ies disc|
|00000250| 20 77 69 6c 6c 20 67 65 | 74 20 79 6f 75 20 73 74 | will ge|t you st|
|00000260| 61 72 74 65 64 2e 20 0d | 49 74 d5 73 20 74 72 69 |arted. .|It.s tri|
|00000270| 63 6b 79 20 74 6f 20 64 | 69 73 70 6c 61 79 20 61 |cky to d|isplay a|
|00000280| 6e 20 69 6d 61 67 65 20 | 77 68 65 6e 20 74 68 65 |n image |when the|
|00000290| 20 6e 75 6d 62 65 72 20 | 6f 66 20 63 6f 6c 6f 72 | number |of color|
|000002a0| 73 20 75 73 65 64 20 69 | 6e 20 74 68 65 20 73 6f |s used i|n the so|
|000002b0| 75 72 63 65 20 65 78 63 | 65 65 64 73 20 74 68 65 |urce exc|eeds the|
|000002c0| 20 6e 75 6d 62 65 72 20 | 6f 66 20 63 6f 6c 6f 72 | number |of color|
|000002d0| 73 20 61 76 61 69 6c 61 | 62 6c 65 20 6f 6e 20 74 |s availa|ble on t|
|000002e0| 68 65 20 64 65 76 69 63 | 65 2e 20 4f 6e 20 61 6e |he devic|e. On an|
|000002f0| 20 69 6e 64 65 78 65 64 | 20 64 65 76 69 63 65 20 | indexed| device |
|00000300| 28 32 35 36 20 6f 72 20 | 66 65 77 65 72 20 63 6f |(256 or |fewer co|
|00000310| 6c 6f 72 73 29 2c 20 61 | 6e 20 61 70 70 6c 69 63 |lors), a|n applic|
|00000320| 61 74 69 6f 6e 20 63 61 | 6e 20 63 68 6f 6f 73 65 |ation ca|n choose|
|00000330| 2c 20 76 69 61 20 74 68 | 65 20 50 61 6c 65 74 74 |, via th|e Palett|
|00000340| 65 20 4d 61 6e 61 67 65 | 72 2c 20 77 68 69 63 68 |e Manage|r, which|
|00000350| 20 63 6f 6c 6f 72 73 20 | 74 6f 20 75 73 65 2e 20 | colors |to use. |
|00000360| 42 75 74 20 68 6f 77 20 | 77 69 6c 6c 20 69 74 20 |But how |will it |
|00000370| 6b 6e 6f 77 20 77 68 69 | 63 68 20 63 6f 6c 6f 72 |know whi|ch color|
|00000380| 73 20 61 72 65 20 74 68 | 65 20 62 65 73 74 20 6f |s are th|e best o|
|00000390| 6e 65 73 20 74 6f 20 63 | 68 6f 6f 73 65 2c 20 67 |nes to c|hoose, g|
|000003a0| 69 76 65 6e 20 61 20 70 | 61 72 74 69 63 75 6c 61 |iven a p|articula|
|000003b0| 72 20 69 6d 61 67 65 3f | 0d 54 6f 20 61 76 6f 69 |r image?|.To avoi|
|000003c0| 64 20 74 68 69 73 20 69 | 73 73 75 65 20 61 6c 74 |d this i|ssue alt|
|000003d0| 6f 67 65 74 68 65 72 2c | 20 79 6f 75 72 20 61 70 |ogether,| your ap|
|000003e0| 70 6c 69 63 61 74 69 6f | 6e 20 63 61 6e 20 73 69 |plicatio|n can si|
|000003f0| 6d 70 6c 79 20 64 72 61 | 77 20 74 68 65 20 69 6d |mply dra|w the im|
|00000400| 61 67 65 20 61 6e 64 20 | 6c 65 74 20 51 75 69 63 |age and |let Quic|
|00000410| 6b 44 72 61 77 20 75 73 | 65 20 69 74 73 20 64 65 |kDraw us|e its de|
|00000420| 66 61 75 6c 74 20 63 6f | 6c 6f 72 20 70 61 6c 65 |fault co|lor pale|
|00000430| 74 74 65 73 20 74 6f 20 | 6d 61 6b 65 20 74 68 65 |ttes to |make the|
|00000440| 20 63 68 6f 69 63 65 2e | 20 42 65 63 61 75 73 65 | choice.| Because|
|00000450| 20 74 68 65 73 65 20 70 | 61 6c 65 74 74 65 73 20 | these p|alettes |
|00000460| 63 6f 6e 74 61 69 6e 20 | 61 20 77 65 6c 6c 2d 64 |contain |a well-d|
|00000470| 69 73 70 65 72 73 65 64 | 20 73 65 74 20 6f 66 20 |ispersed| set of |
|00000480| 63 6f 6c 6f 72 73 2c 20 | 6d 6f 73 74 20 69 6d 61 |colors, |most ima|
|00000490| 67 65 73 20 6c 6f 6f 6b | 20 70 72 65 74 74 79 20 |ges look| pretty |
|000004a0| 67 6f 6f 64 2e 20 48 6f | 77 65 76 65 72 2c 20 69 |good. Ho|wever, i|
|000004b0| 6e 20 74 68 65 20 63 61 | 73 65 20 6f 66 20 61 6e |n the ca|se of an|
|000004c0| 20 69 6d 61 67 65 20 74 | 68 61 74 20 75 73 65 73 | image t|hat uses|
|000004d0| 20 61 6e 20 75 6e 62 61 | 6c 61 6e 63 65 64 20 73 | an unba|lanced s|
|000004e0| 65 74 20 6f 66 20 63 6f | 6c 6f 72 73 2c 20 73 75 |et of co|lors, su|
|000004f0| 63 68 20 61 73 20 61 6e | 20 75 6e 64 65 72 77 61 |ch as an| underwa|
|00000500| 74 65 72 20 73 63 65 6e | 65 20 77 69 74 68 20 6d |ter scen|e with m|
|00000510| 61 6e 79 20 73 75 62 74 | 6c 65 20 73 68 61 64 65 |any subt|le shade|
|00000520| 73 20 6f 66 20 62 6c 75 | 65 2c 20 72 65 6c 79 69 |s of blu|e, relyi|
|00000530| 6e 67 20 6f 6e 20 74 68 | 65 20 64 65 66 61 75 6c |ng on th|e defaul|
|00000540| 74 20 70 61 6c 65 74 74 | 65 20 77 69 6c 6c 20 6e |t palett|e will n|
|00000550| 6f 74 20 70 72 6f 64 75 | 63 65 20 61 20 67 6f 6f |ot produ|ce a goo|
|00000560| 64 2d 6c 6f 6f 6b 69 6e | 67 20 72 65 73 75 6c 74 |d-lookin|g result|
|00000570| 2e 20 49 6e 20 74 68 69 | 73 20 63 61 73 65 2c 20 |. In thi|s case, |
|00000580| 79 6f 75 20 6d 75 73 74 | 20 74 61 63 6b 6c 65 20 |you must| tackle |
|00000590| 74 68 65 20 69 73 73 75 | 65 20 6f 66 20 68 6f 77 |the issu|e of how|
|000005a0| 20 74 6f 20 63 68 6f 6f | 73 65 20 74 68 65 20 6f | to choo|se the o|
|000005b0| 70 74 69 6d 61 6c 20 70 | 61 6c 65 74 74 65 2e 20 |ptimal p|alette. |
|000005c0| 54 68 61 74 d5 73 20 77 | 68 65 6e 20 74 68 65 20 |That.s w|hen the |
|000005d0| 6e 65 77 20 50 69 63 74 | 75 72 65 20 55 74 69 6c |new Pict|ure Util|
|000005e0| 69 74 69 65 73 20 50 61 | 63 6b 61 67 65 20 63 61 |ities Pa|ckage ca|
|000005f0| 6e 20 68 65 6c 70 2e 0d | 50 69 63 74 75 72 65 20 |n help..|Picture |
|00000600| 55 74 69 6c 69 74 69 65 | 73 20 70 72 6f 76 69 64 |Utilitie|s provid|
|00000610| 65 73 20 74 77 6f 20 6d | 65 74 68 6f 64 73 d1 74 |es two m|ethods.t|
|00000620| 68 65 20 70 6f 70 75 6c | 61 72 20 6d 65 74 68 6f |he popul|ar metho|
|00000630| 64 20 61 6e 64 20 74 68 | 65 20 6d 65 64 69 61 6e |d and th|e median|
|00000640| 20 6d 65 74 68 6f 64 d1 | 66 6f 72 20 64 65 74 65 | method.|for dete|
|00000650| 72 6d 69 6e 69 6e 67 20 | 74 68 65 20 62 65 73 74 |rmining |the best|
|00000660| 20 63 6f 6c 6f 72 73 2e | 20 54 68 69 73 20 61 72 | colors.| This ar|
|00000670| 74 69 63 6c 65 20 64 65 | 73 63 72 69 62 65 73 20 |ticle de|scribes |
|00000680| 74 68 65 73 65 20 74 77 | 6f 20 6d 65 74 68 6f 64 |these tw|o method|
|00000690| 73 2e 20 49 6e 20 61 64 | 64 69 74 69 6f 6e 2c 20 |s. In ad|dition, |
|000006a0| 69 74 20 64 65 73 63 72 | 69 62 65 73 20 61 20 74 |it descr|ibes a t|
|000006b0| 68 69 72 64 20 6d 65 74 | 68 6f 64 d1 74 68 65 20 |hird met|hod.the |
|000006c0| 6f 63 74 72 65 65 20 6d | 65 74 68 6f 64 d1 77 68 |octree m|ethod.wh|
|000006d0| 69 63 68 2c 20 69 6e 20 | 61 64 64 69 74 69 6f 6e |ich, in |addition|
|000006e0| 20 74 6f 20 62 65 69 6e | 67 20 75 73 65 66 75 6c | to bein|g useful|
|000006f0| 20 69 6e 20 69 74 73 65 | 6c 66 2c 20 6d 61 6b 65 | in itse|lf, make|
|00000700| 73 20 61 20 63 6f 6e 76 | 65 6e 69 65 6e 74 20 73 |s a conv|enient s|
|00000710| 74 61 72 74 69 6e 67 20 | 70 6f 69 6e 74 20 66 6f |tarting |point fo|
|00000720| 72 20 79 6f 75 20 74 6f | 20 64 65 76 65 6c 6f 70 |r you to| develop|
|00000730| 20 79 6f 75 72 20 6f 77 | 6e 20 61 6c 67 6f 72 69 | your ow|n algori|
|00000740| 74 68 6d 20 66 6f 72 20 | 63 68 6f 6f 73 69 6e 67 |thm for |choosing|
|00000750| 20 74 68 65 20 6f 70 74 | 69 6d 61 6c 20 63 6f 6c | the opt|imal col|
|00000760| 6f 72 20 70 61 6c 65 74 | 74 65 2e 0d 44 45 43 49 |or palet|te..DECI|
|00000770| 44 49 4e 47 20 57 48 49 | 43 48 20 4d 45 54 48 4f |DING WHI|CH METHO|
|00000780| 44 20 54 4f 20 55 53 45 | 0d 49 74 20 77 6f 75 6c |D TO USE|.It woul|
|00000790| 64 20 62 65 20 6e 69 63 | 65 20 69 66 20 6f 6e 65 |d be nic|e if one|
|000007a0| 20 6d 65 74 68 6f 64 20 | 6f 66 20 73 65 6c 65 63 | method |of selec|
|000007b0| 74 69 6e 67 20 63 6f 6c | 6f 72 73 20 77 6f 72 6b |ting col|ors work|
|000007c0| 65 64 20 62 65 73 74 20 | 66 6f 72 20 61 6c 6c 20 |ed best |for all |
|000007d0| 74 79 70 65 73 20 6f 66 | 20 69 6d 61 67 65 73 2e |types of| images.|
|000007e0| 20 42 75 74 20 74 68 65 | 20 74 72 75 74 68 20 69 | But the| truth i|
|000007f0| 73 20 74 68 61 74 20 74 | 68 65 20 6d 65 74 68 6f |s that t|he metho|
|00000800| 64 73 20 70 72 6f 76 69 | 64 65 64 20 69 6e 20 50 |ds provi|ded in P|
|00000810| 69 63 74 75 72 65 20 55 | 74 69 6c 69 74 69 65 73 |icture U|tilities|
|00000820| 20 77 6f 72 6b 20 62 65 | 73 74 20 66 6f 72 20 73 | work be|st for s|
|00000830| 6f 6d 65 0d 74 79 70 65 | 73 20 6f 66 20 69 6d 61 |ome.type|s of ima|
|00000840| 67 65 73 20 28 73 75 63 | 68 20 61 73 20 74 68 6f |ges (suc|h as tho|
|00000850| 73 65 20 77 68 6f 73 65 | 20 63 6f 6c 6f 72 73 20 |se whose| colors |
|00000860| 61 72 65 20 61 6c 6c 20 | 63 6c 75 73 74 65 72 65 |are all |clustere|
|00000870| 64 20 69 6e 20 6f 6e 65 | 20 73 6d 61 6c 6c 20 70 |d in one| small p|
|00000880| 6f 72 74 69 6f 6e 20 6f | 66 20 74 68 65 20 52 47 |ortion o|f the RG|
|00000890| 42 20 63 75 62 65 29 2c | 20 77 68 69 6c 65 20 51 |B cube),| while Q|
|000008a0| 75 69 63 6b 44 72 61 77 | d5 73 20 73 74 61 6e 64 |uickDraw|.s stand|
|000008b0| 61 72 64 20 6d 65 74 68 | 6f 64 20 77 6f 72 6b 73 |ard meth|od works|
|000008c0| 20 62 65 73 74 20 66 6f | 72 20 6f 74 68 65 72 20 | best fo|r other |
|000008d0| 74 79 70 65 73 2e 20 54 | 68 65 72 65 66 6f 72 65 |types. T|herefore|
|000008e0| 2c 20 69 74 d5 73 20 61 | 6c 77 61 79 73 20 69 6d |, it.s a|lways im|
|000008f0| 70 6f 72 74 61 6e 74 20 | 74 6f 20 67 69 76 65 20 |portant |to give |
|00000900| 74 68 65 20 75 73 65 72 | 20 61 20 63 68 6f 69 63 |the user| a choic|
|00000910| 65 20 6f 66 20 77 68 69 | 63 68 20 50 69 63 74 75 |e of whi|ch Pictu|
|00000920| 72 65 20 55 74 69 6c 69 | 74 69 65 73 20 63 6f 6c |re Utili|ties col|
|00000930| 6f 72 2d 70 69 63 6b 69 | 6e 67 20 6d 65 74 68 6f |or-picki|ng metho|
|00000940| 64 20 74 6f 20 75 73 65 | 20 61 6e 64 20 77 68 65 |d to use| and whe|
|00000950| 74 68 65 72 20 74 6f 20 | 75 73 65 20 6f 6e 65 20 |ther to |use one |
|00000960| 6f 66 20 74 68 65 73 65 | 20 61 74 20 61 6c 6c 2e |of these| at all.|
|00000970| 0d 54 68 65 20 74 68 72 | 65 65 20 6d 65 74 68 6f |.The thr|ee metho|
|00000980| 64 73 20 77 65 20 64 69 | 73 63 75 73 73 20 68 65 |ds we di|scuss he|
|00000990| 72 65 20 64 69 66 66 65 | 72 20 69 6e 20 68 6f 77 |re diffe|r in how|
|000009a0| 20 74 68 65 79 20 61 70 | 70 72 6f 78 69 6d 61 74 | they ap|proximat|
|000009b0| 65 20 74 68 65 20 69 64 | 65 61 6c 20 63 6f 6c 6f |e the id|eal colo|
|000009c0| 72 20 73 65 74 2e 20 54 | 68 65 20 70 6f 70 75 6c |r set. T|he popul|
|000009d0| 61 72 20 6d 65 74 68 6f | 64 20 62 61 73 65 73 20 |ar metho|d bases |
|000009e0| 69 74 73 20 63 68 6f 69 | 63 65 73 20 6f 6e 20 61 |its choi|ces on a|
|000009f0| 20 66 72 65 71 75 65 6e | 63 79 20 63 6f 75 6e 74 | frequen|cy count|
|00000a00| 20 6f 66 20 63 6f 6c 6f | 72 73 20 75 73 65 64 20 | of colo|rs used |
|00000a10| 69 6e 20 74 68 65 20 69 | 6d 61 67 65 2c 20 72 65 |in the i|mage, re|
|00000a20| 74 75 72 6e 69 6e 67 20 | 74 68 65 20 6d 6f 73 74 |turning |the most|
|00000a30| 20 66 72 65 71 75 65 6e | 74 6c 79 20 75 73 65 64 | frequen|tly used|
|00000a40| 20 63 6f 6c 6f 72 73 2e | 20 42 6f 74 68 20 74 68 | colors.| Both th|
|00000a50| 65 20 6d 65 64 69 61 6e | 20 61 6e 64 20 6f 63 74 |e median| and oct|
|00000a60| 72 65 65 20 6d 65 74 68 | 6f 64 73 20 61 72 65 20 |ree meth|ods are |
|00000a70| 61 6c 67 6f 72 69 74 68 | 6d 73 20 74 68 61 74 20 |algorith|ms that |
|00000a80| 64 65 73 63 72 69 62 65 | 20 6f 63 63 75 70 61 6e |describe| occupan|
|00000a90| 63 79 20 69 6e 20 61 20 | 73 70 61 63 65 2e 20 49 |cy in a |space. I|
|00000aa0| 6e 20 74 68 69 73 20 63 | 61 73 65 2c 20 74 68 65 |n this c|ase, the|
|00000ab0| 20 73 70 61 63 65 20 69 | 73 20 74 68 65 20 63 6f | space i|s the co|
|00000ac0| 6c 6f 72 20 63 75 62 65 | 20 77 69 74 68 20 61 78 |lor cube| with ax|
|00000ad0| 65 73 20 6f 66 20 72 65 | 64 2c 20 67 72 65 65 6e |es of re|d, green|
|00000ae0| 2c 20 61 6e 64 20 62 6c | 75 65 2c 20 61 6e 64 20 |, and bl|ue, and |
|00000af0| 74 68 65 20 6f 63 63 75 | 70 61 6e 74 73 20 61 72 |the occu|pants ar|
|00000b00| 65 20 74 68 65 20 63 6f | 6c 6f 72 73 20 69 6e 20 |e the co|lors in |
|00000b10| 74 68 65 20 69 6d 61 67 | 65 2e 20 54 68 65 73 65 |the imag|e. These|
|00000b20| 20 61 6c 67 6f 72 69 74 | 68 6d 73 20 64 69 66 66 | algorit|hms diff|
|00000b30| 65 72 20 69 6e 20 74 68 | 65 20 77 61 79 20 74 68 |er in th|e way th|
|00000b40| 65 79 20 64 69 76 69 64 | 65 20 75 70 20 74 68 65 |ey divid|e up the|
|00000b50| 20 73 70 61 63 65 20 69 | 6e 20 6f 72 64 65 72 20 | space i|n order |
|00000b60| 74 6f 20 72 65 74 75 72 | 6e 20 74 68 65 20 63 6f |to retur|n the co|
|00000b70| 72 72 65 63 74 20 6e 75 | 6d 62 65 72 20 6f 66 20 |rrect nu|mber of |
|00000b80| 63 6f 6c 6f 72 73 2e 20 | 54 68 65 20 6d 65 64 69 |colors. |The medi|
|00000b90| 61 6e 20 61 6c 67 6f 72 | 69 74 68 6d 20 73 74 61 |an algor|ithm sta|
|00000ba0| 72 74 73 20 77 69 74 68 | 20 6f 6e 65 20 67 69 61 |rts with| one gia|
|00000bb0| 6e 74 20 62 6f 78 20 63 | 6f 76 65 72 69 6e 67 20 |nt box c|overing |
|00000bc0| 74 68 65 20 65 6e 74 69 | 72 65 20 63 75 62 65 20 |the enti|re cube |
|00000bd0| 61 6e 64 20 73 70 6c 69 | 74 73 20 69 74 20 69 6e |and spli|ts it in|
|00000be0| 74 6f 20 73 75 63 63 65 | 73 73 69 76 65 6c 79 20 |to succe|ssively |
|00000bf0| 73 6d 61 6c 6c 65 72 20 | 62 6f 78 65 73 3b 20 74 |smaller |boxes; t|
|00000c00| 68 65 20 6f 63 74 72 65 | 65 20 61 6c 67 6f 72 69 |he octre|e algori|
|00000c10| 74 68 6d 20 73 74 61 72 | 74 73 20 77 69 74 68 20 |thm star|ts with |
|00000c20| 6c 6f 74 73 20 6f 66 20 | 74 69 6e 79 20 62 6f 78 |lots of |tiny box|
|00000c30| 65 73 20 61 6e 64 20 6a | 6f 69 6e 73 20 74 68 65 |es and j|oins the|
|00000c40| 6d 20 69 6e 74 6f 20 6c | 61 72 67 65 72 20 6f 6e |m into l|arger on|
|00000c50| 65 73 2e 20 42 6f 74 68 | 20 6d 65 74 68 6f 64 73 |es. Both| methods|
|00000c60| 20 72 65 74 75 72 6e 20 | 74 68 65 20 77 65 69 67 | return |the weig|
|00000c70| 68 74 65 64 20 61 76 65 | 72 61 67 65 20 6f 66 20 |hted ave|rage of |
|00000c80| 65 61 63 68 20 6f 66 20 | 74 68 65 20 62 6f 78 65 |each of |the boxe|
|00000c90| 73 20 61 73 20 74 68 65 | 20 66 69 6e 61 6c 20 73 |s as the| final s|
|00000ca0| 65 74 20 6f 66 20 63 6f | 6c 6f 72 73 2e 0d 54 68 |et of co|lors..Th|
|00000cb0| 65 20 6d 6f 73 74 20 61 | 70 70 72 6f 70 72 69 61 |e most a|ppropria|
|00000cc0| 74 65 20 6d 65 74 68 6f | 64 20 66 6f 72 20 79 6f |te metho|d for yo|
|00000cd0| 75 72 20 70 61 72 74 69 | 63 75 6c 61 72 20 75 73 |ur parti|cular us|
|00000ce0| 65 20 64 65 70 65 6e 64 | 73 20 6f 6e 20 66 61 63 |e depend|s on fac|
|00000cf0| 74 6f 72 73 20 73 75 63 | 68 20 61 73 20 74 68 65 |tors suc|h as the|
|00000d00| 20 74 79 70 65 20 6f 66 | 20 69 6d 61 67 65 20 79 | type of| image y|
|00000d10| 6f 75 20 77 61 6e 74 20 | 74 6f 20 64 69 73 70 6c |ou want |to displ|
|00000d20| 61 79 20 28 72 65 61 6c | 20 77 6f 72 6c 64 2c 20 |ay (real| world, |
|00000d30| 63 6f 6d 70 75 74 65 72 | 2d 67 65 6e 65 72 61 74 |computer|-generat|
|00000d40| 65 64 2c 20 67 72 61 70 | 68 69 63 2c 20 61 6e 64 |ed, grap|hic, and|
|00000d50| 20 73 6f 20 6f 6e 29 2c | 20 69 6d 61 67 65 20 63 | so on),| image c|
|00000d60| 6f 6e 74 65 6e 74 20 28 | 70 65 72 68 61 70 73 20 |ontent (|perhaps |
|00000d70| 74 68 65 20 63 6f 6c 6f | 72 73 20 6f 66 20 69 74 |the colo|rs of it|
|00000d80| 65 6d 73 20 69 6e 20 74 | 68 65 20 66 6f 72 65 67 |ems in t|he foreg|
|00000d90| 72 6f 75 6e 64 20 61 72 | 65 20 6d 6f 72 65 20 69 |round ar|e more i|
|00000da0| 6d 70 6f 72 74 61 6e 74 | 20 74 68 61 6e 20 74 68 |mportant| than th|
|00000db0| 65 20 63 6f 6c 6f 72 73 | 20 6f 66 20 69 74 65 6d |e colors| of item|
|00000dc0| 73 20 69 6e 20 74 68 65 | 20 62 61 63 6b 67 72 6f |s in the| backgro|
|00000dd0| 75 6e 64 29 2c 20 6f 72 | 20 65 76 65 6e 20 68 6f |und), or| even ho|
|00000de0| 77 20 74 68 65 20 69 6d | 61 67 65 20 77 69 6c 6c |w the im|age will|
|00000df0| 20 62 65 20 64 69 73 70 | 6c 61 79 65 64 20 28 68 | be disp|layed (h|
|00000e00| 61 6c 66 74 6f 6e 65 64 | 20 6f 72 20 64 69 74 68 |alftoned| or dith|
|00000e10| 65 72 65 64 2c 20 66 6f | 72 20 65 78 61 6d 70 6c |ered, fo|r exampl|
|00000e20| 65 29 2e 20 46 6f 72 20 | 69 6e 73 74 61 6e 63 65 |e). For |instance|
|00000e30| 2c 20 6e 6f 6e 65 20 6f | 66 20 74 68 65 73 65 20 |, none o|f these |
|00000e40| 6d 65 74 68 6f 64 73 20 | 74 61 6b 65 20 64 69 74 |methods |take dit|
|00000e50| 68 65 72 69 6e 67 20 69 | 6e 74 6f 20 61 63 63 6f |hering i|nto acco|
|00000e60| 75 6e 74 2c 20 61 6c 74 | 68 6f 75 67 68 20 73 69 |unt, alt|hough si|
|00000e70| 6e 63 65 20 77 65 20 70 | 72 6f 76 69 64 65 20 79 |nce we p|rovide y|
|00000e80| 6f 75 20 77 69 74 68 20 | 74 68 65 20 73 6f 75 72 |ou with |the sour|
|00000e90| 63 65 20 63 6f 64 65 2c | 20 79 6f 75 20 63 6f 75 |ce code,| you cou|
|00000ea0| 6c 64 20 6d 6f 64 69 66 | 79 20 74 68 65 20 6f 63 |ld modif|y the oc|
|00000eb0| 74 72 65 65 20 6d 65 74 | 68 6f 64 20 74 6f 20 64 |tree met|hod to d|
|00000ec0| 6f 20 73 6f 2e 20 0d 54 | 68 65 20 73 70 65 65 64 |o so. .T|he speed|
|00000ed0| 20 6f 66 20 65 61 63 68 | 20 6d 65 74 68 6f 64 20 | of each| method |
|00000ee0| 61 6c 73 6f 20 76 61 72 | 69 65 73 2c 20 77 69 74 |also var|ies, wit|
|00000ef0| 68 20 74 68 65 20 70 6f | 70 75 6c 61 72 20 6d 65 |h the po|pular me|
|00000f00| 74 68 6f 64 20 62 65 69 | 6e 67 20 66 61 73 74 65 |thod bei|ng faste|
|00000f10| 73 74 2c 20 74 68 65 20 | 6d 65 64 69 61 6e 20 6d |st, the |median m|
|00000f20| 65 74 68 6f 64 20 73 6c | 6f 77 65 72 2c 20 61 6e |ethod sl|ower, an|
|00000f30| 64 20 74 68 65 20 6f 63 | 74 72 65 65 20 6d 65 74 |d the oc|tree met|
|00000f40| 68 6f 64 20 73 6c 6f 77 | 65 73 74 2c 20 73 69 6e |hod slow|est, sin|
|00000f50| 63 65 20 69 6e 20 74 68 | 65 20 6c 61 74 74 65 72 |ce in th|e latter|
|00000f60| 20 74 68 65 72 65 20 61 | 72 65 20 6d 6f 72 65 20 | there a|re more |
|00000f70| 63 61 6c 63 75 6c 61 74 | 69 6f 6e 73 20 69 6e 76 |calculat|ions inv|
|00000f80| 6f 6c 76 65 64 20 66 6f | 72 20 65 61 63 68 20 63 |olved fo|r each c|
|00000f90| 6f 6c 6f 72 20 63 68 6f | 73 65 6e 2e 20 41 6c 73 |olor cho|sen. Als|
|00000fa0| 6f 2c 20 74 68 65 20 63 | 6f 64 65 20 74 68 61 74 |o, the c|ode that|
|00000fb0| 20 77 65 20 73 75 70 70 | 6c 79 20 66 6f 72 20 74 | we supp|ly for t|
|00000fc0| 68 65 20 6f 63 74 72 65 | 65 20 6d 65 74 68 6f 64 |he octre|e method|
|00000fd0| 20 69 73 20 69 6e 74 65 | 6e 64 65 64 20 74 6f 20 | is inte|nded to |
|00000fe0| 62 65 20 65 61 73 79 20 | 74 6f 20 75 6e 64 65 72 |be easy |to under|
|00000ff0| 73 74 61 6e 64 20 72 61 | 74 68 65 72 20 74 68 61 |stand ra|ther tha|
|00001000| 6e 20 62 6c 61 7a 69 6e | 67 6c 79 20 66 61 73 74 |n blazin|gly fast|
|00001010| 2e 20 49 6e 20 66 61 63 | 74 2c 20 74 68 65 20 63 |. In fac|t, the c|
|00001020| 75 72 72 65 6e 74 20 63 | 6f 64 65 20 69 73 20 73 |urrent c|ode is s|
|00001030| 6c 6f 77 65 72 20 74 68 | 61 6e 20 74 68 65 20 70 |lower th|an the p|
|00001040| 6f 70 75 6c 61 72 20 6d | 65 74 68 6f 64 20 62 79 |opular m|ethod by|
|00001050| 20 61 20 66 61 63 74 6f | 72 20 6f 66 20 66 6f 75 | a facto|r of fou|
|00001060| 72 2c 20 62 75 74 20 77 | 69 74 68 20 61 20 6c 69 |r, but w|ith a li|
|00001070| 74 74 6c 65 20 77 6f 72 | 6b 20 74 68 69 73 20 63 |ttle wor|k this c|
|00001080| 6f 75 6c 64 20 70 72 6f | 62 61 62 6c 79 20 62 65 |ould pro|bably be|
|00001090| 20 69 6d 70 72 6f 76 65 | 64 20 74 6f 20 62 65 20 | improve|d to be |
|000010a0| 6f 6e 6c 79 20 74 77 69 | 63 65 20 61 73 20 73 6c |only twi|ce as sl|
|000010b0| 6f 77 2e 0d 41 6e 6f 74 | 68 65 72 20 62 61 73 69 |ow..Anot|her basi|
|000010c0| 63 20 63 6f 6e 73 69 64 | 65 72 61 74 69 6f 6e 20 |c consid|eration |
|000010d0| 69 73 20 77 68 65 74 68 | 65 72 20 79 6f 75 20 77 |is wheth|er you w|
|000010e0| 61 6e 74 20 74 6f 20 72 | 65 70 72 65 73 65 6e 74 |ant to r|epresent|
|000010f0| 20 74 68 65 20 6d 61 6a | 6f 72 69 74 79 20 6f 66 | the maj|ority of|
|00001100| 20 63 6f 6c 6f 72 73 20 | 69 6e 20 74 68 65 20 69 | colors |in the i|
|00001110| 6d 61 67 65 20 6f 72 20 | 74 68 65 20 72 61 6e 67 |mage or |the rang|
|00001120| 65 20 6f 66 20 63 6f 6c | 6f 72 73 20 70 72 65 73 |e of col|ors pres|
|00001130| 65 6e 74 2e 20 46 6f 72 | 20 65 78 61 6d 70 6c 65 |ent. For| example|
|00001140| 2c 20 69 66 20 79 6f 75 | 20 63 6f 75 6c 64 20 73 |, if you| could s|
|00001150| 65 6c 65 63 74 20 6f 6e | 6c 79 20 74 77 6f 20 63 |elect on|ly two c|
|00001160| 6f 6c 6f 72 73 20 74 6f | 20 72 65 70 72 65 73 65 |olors to| represe|
|00001170| 6e 74 20 61 6e 20 69 6d | 61 67 65 20 74 68 61 74 |nt an im|age that|
|00001180| 20 63 6f 6e 74 61 69 6e | 73 20 73 65 76 65 72 61 | contain|s severa|
|00001190| 6c 20 64 69 66 66 65 72 | 65 6e 74 20 73 68 61 64 |l differ|ent shad|
|000011a0| 65 73 20 6f 66 20 72 65 | 64 20 61 6e 64 20 6f 6e |es of re|d and on|
|000011b0| 65 20 62 6c 75 65 20 64 | 6f 74 2c 20 79 6f 75 20 |e blue d|ot, you |
|000011c0| 77 6f 75 6c 64 20 68 61 | 76 65 20 74 6f 20 64 65 |would ha|ve to de|
|000011d0| 63 69 64 65 20 77 68 65 | 74 68 65 72 20 74 6f 20 |cide whe|ther to |
|000011e0| 70 69 63 6b 20 74 77 6f | 20 72 65 64 73 20 69 6e |pick two| reds in|
|000011f0| 20 61 6e 20 61 74 74 65 | 6d 70 74 20 74 6f 20 72 | an atte|mpt to r|
|00001200| 65 70 72 65 73 65 6e 74 | 20 74 68 65 20 6d 61 6a |epresent| the maj|
|00001210| 6f 72 69 74 79 20 6f 66 | 20 63 6f 6c 6f 72 73 20 |ority of| colors |
|00001220| 69 6e 20 74 68 65 20 69 | 6d 61 67 65 2c 20 6f 72 |in the i|mage, or|
|00001230| 20 6f 6e 65 20 72 65 64 | 20 61 6e 64 20 6f 6e 65 | one red| and one|
|00001240| 20 62 6c 75 65 20 74 6f | 20 72 65 70 72 65 73 65 | blue to| represe|
|00001250| 6e 74 20 74 68 65 20 72 | 61 6e 67 65 20 6f 66 20 |nt the r|ange of |
|00001260| 63 6f 6c 6f 72 73 20 74 | 68 65 20 69 6d 61 67 65 |colors t|he image|
|00001270| 20 63 6f 6e 74 61 69 6e | 73 2e 20 54 68 65 20 70 | contain|s. The p|
|00001280| 6f 70 75 6c 61 72 20 6d | 65 74 68 6f 64 20 77 6f |opular m|ethod wo|
|00001290| 75 6c 64 20 64 6f 20 74 | 68 65 20 66 6f 72 6d 65 |uld do t|he forme|
|000012a0| 72 2c 20 77 68 69 6c 65 | 20 74 68 65 20 6d 65 64 |r, while| the med|
|000012b0| 69 61 6e 20 6d 65 74 68 | 6f 64 20 77 6f 75 6c 64 |ian meth|od would|
|000012c0| 20 64 6f 20 74 68 65 20 | 6c 61 74 74 65 72 2e 20 | do the |latter. |
|000012d0| 0d 49 6e 20 67 65 6e 65 | 72 61 6c 2c 20 74 68 65 |.In gene|ral, the|
|000012e0| 20 62 65 73 74 20 6d 65 | 74 68 6f 64 20 74 6f 20 | best me|thod to |
|000012f0| 75 73 65 20 66 6f 72 20 | 61 6e 20 69 6d 61 67 65 |use for |an image|
|00001300| 20 74 68 61 74 20 68 61 | 73 20 61 20 66 61 69 72 | that ha|s a fair|
|00001310| 6c 79 20 77 65 6c 6c 20 | 64 69 73 70 65 72 73 65 |ly well |disperse|
|00001320| 64 20 73 65 74 20 6f 66 | 20 63 6f 6c 6f 72 73 20 |d set of| colors |
|00001330| 69 73 20 51 75 69 63 6b | 44 72 61 77 d5 73 20 64 |is Quick|Draw.s d|
|00001340| 65 66 61 75 6c 74 20 70 | 61 6c 65 74 74 65 2e 20 |efault p|alette. |
|00001350| 54 68 65 20 70 6f 70 75 | 6c 61 72 20 6d 65 74 68 |The popu|lar meth|
|00001360| 6f 64 20 69 73 20 75 73 | 65 66 75 6c 20 77 68 65 |od is us|eful whe|
|00001370| 6e 20 74 68 65 20 73 6f | 75 72 63 65 20 69 6d 61 |n the so|urce ima|
|00001380| 67 65 20 63 6f 6e 74 61 | 69 6e 73 20 6f 6e 6c 79 |ge conta|ins only|
|00001390| 20 61 20 66 65 77 20 6d | 6f 72 65 20 63 6f 6c 6f | a few m|ore colo|
|000013a0| 72 73 20 74 68 61 6e 20 | 61 72 65 20 61 76 61 69 |rs than |are avai|
|000013b0| 6c 61 62 6c 65 20 6f 6e | 20 74 68 65 20 64 69 73 |lable on| the dis|
|000013c0| 70 6c 61 79 20 64 65 76 | 69 63 65 2e 20 46 6f 72 |play dev|ice. For|
|000013d0| 20 65 78 61 6d 70 6c 65 | 2c 20 69 66 20 79 6f 75 | example|, if you|
|000013e0| 20 77 61 6e 74 20 74 6f | 20 64 69 73 70 6c 61 79 | want to| display|
|000013f0| 20 61 20 33 32 2d 62 69 | 74 20 69 6d 61 67 65 20 | a 32-bi|t image |
|00001400| 74 68 61 74 20 75 73 65 | 73 20 6f 6e 6c 79 20 32 |that use|s only 2|
|00001410| 30 30 20 64 69 73 74 69 | 6e 63 74 20 63 6f 6c 6f |00 disti|nct colo|
|00001420| 72 73 20 6f 6e 20 61 6e | 20 38 2d 62 69 74 20 64 |rs on an| 8-bit d|
|00001430| 65 76 69 63 65 2c 20 74 | 68 65 20 70 6f 70 75 6c |evice, t|he popul|
|00001440| 61 72 20 6d 65 74 68 6f | 64 20 69 73 20 74 68 65 |ar metho|d is the|
|00001450| 20 62 65 73 74 20 63 68 | 6f 69 63 65 20 66 6f 72 | best ch|oice for|
|00001460| 20 73 70 65 65 64 20 61 | 6e 64 20 61 63 63 75 72 | speed a|nd accur|
|00001470| 61 63 79 2e 20 57 68 69 | 6c 65 20 74 68 69 73 20 |acy. Whi|le this |
|00001480| 63 61 73 65 20 69 73 20 | 74 72 69 76 69 61 6c 2c |case is |trivial,|
|00001490| 20 75 73 69 6e 67 20 74 | 68 65 20 70 6f 70 75 6c | using t|he popul|
|000014a0| 61 72 20 6d 65 74 68 6f | 64 20 64 6f 65 73 20 67 |ar metho|d does g|
|000014b0| 75 61 72 61 6e 74 65 65 | 20 74 68 61 74 20 74 68 |uarantee| that th|
|000014c0| 65 20 6e 65 65 64 65 64 | 20 63 6f 6c 6f 72 73 20 |e needed| colors |
|000014d0| 77 69 6c 6c 20 62 65 20 | 0d 6d 61 64 65 20 61 76 |will be |.made av|
|000014e0| 61 69 6c 61 62 6c 65 2c | 20 61 20 63 6c 61 69 6d |ailable,| a claim|
|000014f0| 20 74 68 61 74 20 63 61 | 6e d5 74 20 62 65 20 6d | that ca|n.t be m|
|00001500| 61 64 65 20 66 6f 72 20 | 74 68 65 20 64 65 66 61 |ade for |the defa|
|00001510| 75 6c 74 20 70 61 6c 65 | 74 74 65 2e 20 54 68 65 |ult pale|tte. The|
|00001520| 20 6d 65 64 69 61 6e 20 | 61 6e 64 20 6f 63 74 72 | median |and octr|
|00001530| 65 65 20 6d 65 74 68 6f | 64 73 20 67 65 6e 65 72 |ee metho|ds gener|
|00001540| 61 6c 6c 79 20 67 69 76 | 65 20 74 68 65 20 62 65 |ally giv|e the be|
|00001550| 73 74 20 72 65 73 75 6c | 74 73 20 66 6f 72 20 69 |st resul|ts for i|
|00001560| 6d 61 67 65 73 20 77 68 | 65 72 65 20 73 6d 61 6c |mages wh|ere smal|
|00001570| 6c 20 70 61 74 63 68 65 | 73 20 6f 66 20 61 20 64 |l patche|s of a d|
|00001580| 69 73 74 69 6e 63 74 6c | 79 20 64 69 66 66 65 72 |istinctl|y differ|
|00001590| 65 6e 74 20 63 6f 6c 6f | 72 20 6d 75 73 74 20 62 |ent colo|r must b|
|000015a0| 65 20 70 72 65 73 65 72 | 76 65 64 20 61 74 20 74 |e preser|ved at t|
|000015b0| 68 65 20 63 6f 73 74 20 | 6f 66 20 62 6c 65 6e 64 |he cost |of blend|
|000015c0| 69 6e 67 20 74 6f 67 65 | 74 68 65 72 20 6c 61 72 |ing toge|ther lar|
|000015d0| 67 65 20 70 61 74 63 68 | 65 73 20 6f 66 20 73 69 |ge patch|es of si|
|000015e0| 6d 69 6c 61 72 20 63 6f | 6c 6f 72 73 2e 20 0d 45 |milar co|lors. .E|
|000015f0| 78 70 65 72 69 65 6e 63 | 65 20 77 69 6c 6c 20 67 |xperienc|e will g|
|00001600| 69 76 65 20 79 6f 75 20 | 61 20 62 65 74 74 65 72 |ive you |a better|
|00001610| 20 66 65 65 6c 20 66 6f | 72 20 74 68 65 20 73 74 | feel fo|r the st|
|00001620| 72 65 6e 67 74 68 73 20 | 61 6e 64 20 77 65 61 6b |rengths |and weak|
|00001630| 6e 65 73 73 65 73 20 6f | 66 20 65 61 63 68 20 6f |nesses o|f each o|
|00001640| 66 20 74 68 65 73 65 20 | 6d 65 74 68 6f 64 73 2e |f these |methods.|
|00001650| 20 4d 65 61 6e 77 68 69 | 6c 65 2c 20 66 6f 72 20 | Meanwhi|le, for |
|00001660| 70 75 72 70 6f 73 65 73 | 20 6f 66 20 63 6f 6d 70 |purposes| of comp|
|00001670| 61 72 69 73 6f 6e 2c 20 | 46 69 67 75 72 65 20 31 |arison, |Figure 1|
|00001680| 20 73 68 6f 77 73 20 73 | 63 72 65 65 6e 20 73 6e | shows s|creen sn|
|00001690| 61 70 73 68 6f 74 73 20 | 6f 66 20 61 20 33 32 2d |apshots |of a 32-|
|000016a0| 62 69 74 20 69 6d 61 67 | 65 20 61 73 20 69 74 20 |bit imag|e as it |
|000016b0| 6f 72 69 67 69 6e 61 6c | 6c 79 20 61 70 70 65 61 |original|ly appea|
|000016c0| 72 65 64 2c 20 75 73 69 | 6e 67 20 51 75 69 63 6b |red, usi|ng Quick|
|000016d0| 44 72 61 77 d5 73 20 64 | 65 66 61 75 6c 74 20 31 |Draw.s d|efault 1|
|000016e0| 36 2d 63 6f 6c 6f 72 20 | 70 61 6c 65 74 74 65 2c |6-color |palette,|
|000016f0| 20 75 73 69 6e 67 20 31 | 36 20 70 6f 70 75 6c 61 | using 1|6 popula|
|00001700| 72 20 63 6f 6c 6f 72 73 | 2c 20 75 73 69 6e 67 20 |r colors|, using |
|00001710| 31 36 20 6d 65 64 69 61 | 6e 20 63 6f 6c 6f 72 73 |16 media|n colors|
|00001720| 2c 20 61 6e 64 20 75 73 | 69 6e 67 20 31 36 20 6f |, and us|ing 16 o|
|00001730| 63 74 72 65 65 20 63 6f | 6c 6f 72 73 2e 20 54 68 |ctree co|lors. Th|
|00001740| 65 20 6f 72 69 67 69 6e | 61 6c 20 69 6d 61 67 65 |e origin|al image|
|00001750| 20 68 61 73 20 37 37 20 | 64 69 66 66 65 72 65 6e | has 77 |differen|
|00001760| 74 20 63 6f 6c 6f 72 73 | 20 28 74 6f 20 61 20 72 |t colors| (to a r|
|00001770| 65 73 6f 6c 75 74 69 6f | 6e 20 6f 66 20 66 69 76 |esolutio|n of fiv|
|00001780| 65 20 62 69 74 73 20 70 | 65 72 20 63 6f 6c 6f 72 |e bits p|er color|
|00001790| 20 63 6f 6d 70 6f 6e 65 | 6e 74 29 2e 20 41 20 74 | compone|nt). A t|
|000017a0| 65 73 74 20 70 72 6f 67 | 72 61 6d 20 6f 6e 20 74 |est prog|ram on t|
|000017b0| 68 65 20 44 65 76 65 6c | 6f 70 65 72 20 43 44 20 |he Devel|oper CD |
|000017c0| 53 65 72 69 65 73 20 64 | 69 73 63 20 65 6e 61 62 |Series d|isc enab|
|000017d0| 6c 65 73 20 79 6f 75 20 | 74 6f 20 65 78 70 65 72 |les you |to exper|
|000017e0| 69 6d 65 6e 74 20 77 69 | 74 68 20 74 68 69 73 20 |iment wi|th this |
|000017f0| 69 6d 61 67 65 20 28 6f | 72 20 6f 74 68 65 72 73 |image (o|r others|
|00001800| 29 20 61 6e 64 20 74 6f | 20 74 61 6b 65 20 61 20 |) and to| take a |
|00001810| 6c 6f 6f 6b 20 61 74 20 | 74 68 65 20 63 6f 64 65 |look at |the code|
|00001820| 20 75 73 65 64 20 74 6f | 20 67 65 6e 65 72 61 74 | used to| generat|
|00001830| 65 20 74 68 65 20 76 61 | 72 69 6f 75 73 20 76 65 |e the va|rious ve|
|00001840| 72 73 69 6f 6e 73 2e 0d | 4e 6f 74 69 63 65 20 69 |rsions..|Notice i|
|00001850| 6e 20 74 68 65 20 6f 72 | 69 67 69 6e 61 6c 20 69 |n the or|iginal i|
|00001860| 6d 61 67 65 20 74 68 61 | 74 20 74 68 65 20 63 6f |mage tha|t the co|
|00001870| 6c 6f 72 73 20 6d 61 72 | 6b 69 6e 67 20 74 68 65 |lors mar|king the|
|00001880| 20 6d 69 6e 75 74 65 73 | 20 66 6f 6c 6c 6f 77 20 | minutes| follow |
|00001890| 61 20 73 6d 6f 6f 74 68 | 20 70 72 6f 67 72 65 73 |a smooth| progres|
|000018a0| 73 69 6f 6e 20 66 72 6f | 6d 20 63 79 61 6e 20 6f |sion fro|m cyan o|
|000018b0| 6e 20 74 68 65 20 66 61 | 72 20 6c 65 66 74 20 74 |n the fa|r left t|
|000018c0| 6f 20 64 61 72 6b 20 62 | 6c 75 65 20 61 74 20 74 |o dark b|lue at t|
|000018d0| 68 65 20 74 6f 70 20 74 | 6f 20 6d 61 67 65 6e 74 |he top t|o magent|
|000018e0| 61 20 6f 6e 20 74 68 65 | 20 72 69 67 68 74 20 74 |a on the| right t|
|000018f0| 6f 20 70 75 72 70 6c 65 | 20 6f 6e 20 74 68 65 20 |o purple| on the |
|00001900| 62 6f 74 74 6f 6d 20 61 | 6e 64 20 74 68 65 6e 20 |bottom a|nd then |
|00001910| 74 6f 20 64 61 72 6b 20 | 72 65 64 20 6a 75 73 74 |to dark |red just|
|00001920| 20 62 65 66 6f 72 65 20 | 74 68 65 20 63 79 61 6e | before |the cyan|
|00001930| 2e 20 41 6c 73 6f 20 6e | 6f 74 69 63 65 20 74 68 |. Also n|otice th|
|00001940| 65 20 73 75 62 74 6c 65 | 20 63 6f 6c 6f 72 20 62 |e subtle| color b|
|00001950| 6c 65 6e 64 69 6e 67 20 | 77 68 65 72 65 20 74 68 |lending |where th|
|00001960| 65 20 74 72 61 6e 73 6c | 75 63 65 6e 74 20 6d 69 |e transl|ucent mi|
|00001970| 6e 75 74 65 20 61 6e 64 | 20 73 65 63 6f 6e 64 20 |nute and| second |
|00001980| 68 61 6e 64 73 20 69 6e | 74 65 72 73 65 63 74 20 |hands in|tersect |
|00001990| 74 68 65 20 75 6e 64 65 | 72 6c 79 69 6e 67 20 63 |the unde|rlying c|
|000019a0| 6c 6f 63 6b 2e 20 57 68 | 65 6e 20 74 68 65 20 73 |lock. Wh|en the s|
|000019b0| 74 61 6e 64 61 72 64 20 | 31 36 2d 63 6f 6c 6f 72 |tandard |16-color|
|000019c0| 20 70 61 6c 65 74 74 65 | 20 69 73 20 75 73 65 64 | palette| is used|
|000019d0| 2c 20 74 68 65 20 73 6f | 66 74 20 63 6f 6c 6f 72 |, the so|ft color|
|000019e0| 73 20 6f 66 20 74 68 65 | 20 6d 69 6e 75 74 65 20 |s of the| minute |
|000019f0| 6d 61 72 6b 65 72 73 20 | 63 68 61 6e 67 65 20 69 |markers |change i|
|00001a00| 6e 74 6f 20 6d 75 63 68 | 20 62 72 69 67 68 74 65 |nto much| brighte|
|00001a10| 72 2c 20 68 61 72 64 65 | 72 20 63 6f 6c 6f 72 73 |r, harde|r colors|
|00001a20| 2c 20 61 6e 64 20 74 68 | 65 20 73 6d 6f 6f 74 68 |, and th|e smooth|
|00001a30| 20 74 72 61 6e 73 69 74 | 69 6f 6e 73 20 61 72 65 | transit|ions are|
|00001a40| 20 72 65 70 6c 61 63 65 | 64 20 62 79 20 73 75 64 | replace|d by sud|
|00001a50| 64 65 6e 20 74 72 61 6e | 73 69 74 69 6f 6e 73 2e |den tran|sitions.|
|00001a60| 20 54 68 65 20 63 6f 6c | 6f 72 73 20 6f 66 20 74 | The col|ors of t|
|00001a70| 68 65 20 62 61 63 6b 67 | 72 6f 75 6e 64 20 61 6e |he backg|round an|
|00001a80| 64 20 74 68 65 20 66 61 | 63 65 20 6f 66 20 74 68 |d the fa|ce of th|
|00001a90| 65 20 63 6c 6f 63 6b 20 | 68 61 76 65 20 63 68 61 |e clock |have cha|
|00001aa0| 6e 67 65 64 2e 20 46 75 | 72 74 68 65 72 6d 6f 72 |nged. Fu|rthermor|
|00001ab0| 65 2c 20 74 68 65 20 73 | 75 62 74 6c 65 20 64 69 |e, the s|ubtle di|
|00001ac0| 66 66 65 72 65 6e 63 65 | 20 69 6e 20 63 6f 6c 6f |fference| in colo|
|00001ad0| 72 20 62 65 74 77 65 65 | 6e 20 74 68 65 20 62 61 |r betwee|n the ba|
|00001ae0| 63 6b 67 72 6f 75 6e 64 | 20 61 6e 64 20 74 68 65 |ckground| and the|
|00001af0| 20 62 61 63 6b 67 72 6f | 75 6e 64 20 6f 66 20 74 | backgro|und of t|
|00001b00| 68 65 20 64 61 74 65 20 | 28 4a 61 6e 75 61 72 79 |he date |(January|
|00001b10| 20 32 34 29 20 69 73 20 | 6c 6f 73 74 2e 20 0d 54 | 24) is |lost. .T|
|00001b20| 68 65 20 70 6f 70 75 6c | 61 72 20 6d 65 74 68 6f |he popul|ar metho|
|00001b30| 64 20 70 72 65 73 65 72 | 76 65 73 20 74 68 65 20 |d preser|ves the |
|00001b40| 63 6f 6c 6f 72 73 20 6f | 66 20 74 68 65 20 6c 61 |colors o|f the la|
|00001b50| 72 67 65 73 74 20 63 6f | 6c 6f 72 20 61 72 65 61 |rgest co|lor area|
|00001b60| 73 3a 20 74 68 65 20 62 | 61 63 6b 67 72 6f 75 6e |s: the b|ackgroun|
|00001b70| 64 2c 20 74 68 65 20 63 | 6c 6f 63 6b 20 66 61 63 |d, the c|lock fac|
|00001b80| 65 2c 20 74 68 65 20 62 | 61 63 6b 67 72 6f 75 6e |e, the b|ackgroun|
|00001b90| 64 20 6f 66 20 74 68 65 | 20 64 61 74 65 2c 20 74 |d of the| date, t|
|00001ba0| 68 65 20 63 6f 6c 6f 72 | 20 6f 66 20 74 68 65 20 |he color| of the |
|00001bb0| 6d 69 6e 75 74 65 20 61 | 6e 64 20 68 6f 75 72 20 |minute a|nd hour |
|00001bc0| 68 61 6e 64 73 2c 20 61 | 6e 64 20 74 68 65 20 6c |hands, a|nd the l|
|00001bd0| 65 74 74 65 72 69 6e 67 | 2e 20 54 68 65 20 63 6f |ettering|. The co|
|00001be0| 6c 6f 72 73 20 6f 66 20 | 74 68 65 20 6d 69 6e 75 |lors of |the minu|
|00001bf0| 74 65 20 6d 61 72 6b 65 | 72 73 20 72 65 6d 61 69 |te marke|rs remai|
|00001c00| 6e 20 73 6f 66 74 2c 20 | 62 75 74 20 6c 6f 73 65 |n soft, |but lose|
|00001c10| 20 74 68 65 69 72 20 73 | 68 61 64 69 6e 67 20 72 | their s|hading r|
|00001c20| 65 73 6f 6c 75 74 69 6f | 6e 3b 20 66 6f 72 20 65 |esolutio|n; for e|
|00001c30| 78 61 6d 70 6c 65 2c 20 | 74 68 65 20 63 79 61 6e |xample, |the cyan|
|00001c40| 20 69 73 20 72 65 70 6c | 61 63 65 64 20 62 79 20 | is repl|aced by |
|00001c50| 61 20 64 61 72 6b 65 72 | 20 62 6c 75 65 2e 20 42 |a darker| blue. B|
|00001c60| 65 63 61 75 73 65 20 69 | 74 20 70 72 65 73 65 72 |ecause i|t preser|
|00001c70| 76 65 73 20 74 68 65 20 | 72 61 6e 67 65 20 6f 66 |ves the |range of|
|00001c80| 20 63 6f 6c 6f 72 73 2c | 20 74 68 65 20 6d 65 64 | colors,| the med|
|00001c90| 69 61 6e 20 6d 65 74 68 | 6f 64 20 70 65 72 66 6f |ian meth|od perfo|
|00001ca0| 72 6d 73 20 73 6f 6d 65 | 77 68 61 74 20 62 65 74 |rms some|what bet|
|00001cb0| 74 65 72 20 6f 6e 20 74 | 68 65 20 6d 69 6e 75 74 |ter on t|he minut|
|00001cc0| 65 20 6d 61 72 6b 65 72 | 73 20 74 68 61 6e 20 74 |e marker|s than t|
|00001cd0| 68 65 20 70 72 65 76 69 | 6f 75 73 20 74 77 6f 20 |he previ|ous two |
|00001ce0| 6d 65 74 68 6f 64 73 2c | 20 62 75 74 20 74 68 65 |methods,| but the|
|00001cf0| 20 63 6c 6f 63 6b 20 66 | 61 63 65 20 74 75 72 6e | clock f|ace turn|
|00001d00| 73 20 74 6f 20 62 6c 61 | 63 6b 20 61 6e 64 20 74 |s to bla|ck and t|
|00001d10| 68 65 20 67 72 65 65 6e | 20 68 61 6e 64 20 62 65 |he green| hand be|
|00001d20| 63 6f 6d 65 73 20 77 61 | 73 68 65 64 20 6f 75 74 |comes wa|shed out|
|00001d30| 2e 20 41 6c 74 68 6f 75 | 67 68 20 74 68 65 20 69 |. Althou|gh the i|
|00001d40| 6d 61 67 65 d5 73 20 61 | 70 70 65 61 72 61 6e 63 |mage.s a|ppearanc|
|00001d50| 65 20 6d 61 79 20 6e 6f | 74 20 62 65 20 69 64 65 |e may no|t be ide|
|00001d60| 61 6c 20 62 65 63 61 75 | 73 65 20 6d 61 6e 79 20 |al becau|se many |
|00001d70| 6f 66 20 74 68 65 20 6c | 61 72 67 65 20 61 72 65 |of the l|arge are|
|00001d80| 61 73 20 61 72 65 20 77 | 72 6f 6e 67 2c 20 61 72 |as are w|rong, ar|
|00001d90| 65 61 73 20 6f 66 20 74 | 68 65 20 69 6d 61 67 65 |eas of t|he image|
|00001da0| 20 74 68 61 74 20 64 65 | 70 65 6e 64 20 6f 6e 20 | that de|pend on |
|00001db0| 74 68 65 20 63 6f 6c 6f | 72 20 72 61 6e 67 65 73 |the colo|r ranges|
|00001dc0| 20 28 77 68 69 63 68 20 | 69 6e 20 74 68 69 73 20 | (which |in this |
|00001dd0| 69 6d 61 67 65 20 6a 75 | 73 74 20 68 61 70 70 65 |image ju|st happe|
|00001de0| 6e 20 74 6f 20 6f 63 63 | 75 70 79 20 73 6d 61 6c |n to occ|upy smal|
|00001df0| 6c 20 61 72 65 61 73 29 | 20 61 72 65 20 72 65 70 |l areas)| are rep|
|00001e00| 72 6f 64 75 63 65 64 20 | 6d 6f 72 65 20 61 63 63 |roduced |more acc|
|00001e10| 75 72 61 74 65 6c 79 2e | 20 57 68 65 6e 20 74 68 |urately.| When th|
|00001e20| 65 20 6f 63 74 72 65 65 | 20 6d 65 74 68 6f 64 20 |e octree| method |
|00001e30| 69 73 20 75 73 65 64 2c | 20 74 68 65 20 72 65 73 |is used,| the res|
|00001e40| 75 6c 74 20 69 73 20 73 | 69 6d 69 6c 61 72 20 74 |ult is s|imilar t|
|00001e50| 6f 20 74 68 61 74 20 6f | 66 20 74 68 65 20 6d 65 |o that o|f the me|
|00001e60| 64 69 61 6e 20 6d 65 74 | 68 6f 64 2c 20 65 78 63 |dian met|hod, exc|
|00001e70| 65 70 74 20 74 68 65 20 | 67 72 65 65 6e 20 68 6f |ept the |green ho|
|00001e80| 75 72 20 68 61 6e 64 20 | 69 73 20 63 6f 6d 70 6c |ur hand |is compl|
|00001e90| 65 74 65 6c 79 20 6c 6f | 73 74 2e 20 54 68 69 73 |etely lo|st. This|
|00001ea0| 20 69 73 20 64 75 65 20 | 74 6f 20 74 68 65 20 73 | is due |to the s|
|00001eb0| 69 6d 70 6c 65 20 74 72 | 65 65 20 72 65 64 75 63 |imple tr|ee reduc|
|00001ec0| 74 69 6f 6e 20 61 6c 67 | 6f 72 69 74 68 6d 20 77 |tion alg|orithm w|
|00001ed0| 65 20 75 73 65 3b 20 69 | 66 20 74 68 65 20 74 72 |e use; i|f the tr|
|00001ee0| 65 65 20 72 65 64 75 63 | 74 69 6f 6e 20 69 6d 70 |ee reduc|tion imp|
|00001ef0| 72 6f 76 65 6d 65 6e 74 | 73 20 74 68 61 74 20 77 |rovement|s that w|
|00001f00| 65 20 73 75 67 67 65 73 | 74 20 61 74 20 74 68 65 |e sugges|t at the|
|00001f10| 20 65 6e 64 20 6f 66 20 | 74 68 65 20 61 72 74 69 | end of |the arti|
|00001f20| 63 6c 65 20 77 65 72 65 | 20 69 6d 70 6c 65 6d 65 |cle were| impleme|
|00001f30| 6e 74 65 64 2c 20 74 68 | 65 20 68 6f 75 72 20 68 |nted, th|e hour h|
|00001f40| 61 6e 64 20 6d 6f 73 74 | 20 6c 69 6b 65 6c 79 20 |and most| likely |
|00001f50| 77 6f 75 6c 64 20 62 65 | 20 70 72 65 73 65 72 76 |would be| preserv|
|00001f60| 65 64 2c 20 61 6c 74 68 | 6f 75 67 68 20 69 74 73 |ed, alth|ough its|
|00001f70| 20 73 68 61 64 65 20 6f | 66 20 67 72 65 65 6e 20 | shade o|f green |
|00001f80| 6d 69 67 68 74 20 63 68 | 61 6e 67 65 20 28 6d 75 |might ch|ange (mu|
|00001f90| 63 68 20 61 73 20 68 61 | 70 70 65 6e 65 64 20 77 |ch as ha|ppened w|
|00001fa0| 69 74 68 20 74 68 65 20 | 6d 65 64 69 61 6e 20 6d |ith the |median m|
|00001fb0| 65 74 68 6f 64 29 2e 20 | 54 68 65 20 6f 63 74 72 |ethod). |The octr|
|00001fc0| 65 65 20 70 65 72 66 6f | 72 6d 65 64 20 62 65 74 |ee perfo|rmed bet|
|00001fd0| 74 65 72 20 74 68 61 6e | 20 74 68 65 20 6d 65 64 |ter than| the med|
|00001fe0| 69 61 6e 20 69 6e 20 70 | 72 65 73 65 72 76 69 6e |ian in p|reservin|
|00001ff0| 67 20 74 68 65 20 63 6f | 6c 6f 72 20 6f 66 20 74 |g the co|lor of t|
|00002000| 68 65 20 74 65 78 74 20 | 61 6e 64 20 74 68 65 20 |he text |and the |
|00002010| 62 61 63 6b 67 72 6f 75 | 6e 64 20 6f 66 20 74 68 |backgrou|nd of th|
|00002020| 65 20 64 61 74 65 2e 20 | 0d 4f 6e 65 20 63 6f 6e |e date. |.One con|
|00002030| 63 6c 75 73 69 6f 6e 20 | 66 72 6f 6d 20 74 68 65 |clusion |from the|
|00002040| 73 65 20 69 6d 61 67 65 | 73 20 69 73 20 74 68 61 |se image|s is tha|
|00002050| 74 20 74 68 65 72 65 20 | 69 73 20 6e 6f 74 20 61 |t there |is not a|
|00002060| 20 73 69 6e 67 6c 65 20 | 62 65 73 74 20 63 6f 6c | single |best col|
|00002070| 6f 72 2d 70 69 63 6b 69 | 6e 67 20 61 6c 67 6f 72 |or-picki|ng algor|
|00002080| 69 74 68 6d 2c 20 65 76 | 65 6e 20 66 6f 72 20 61 |ithm, ev|en for a|
|00002090| 20 70 61 72 74 69 63 75 | 6c 61 72 20 70 69 63 74 | particu|lar pict|
|000020a0| 75 72 65 2e 20 46 6f 72 | 20 74 68 69 73 20 69 6d |ure. For| this im|
|000020b0| 61 67 65 2c 20 77 65 20 | 77 6f 75 6c 64 20 62 65 |age, we |would be|
|000020c0| 20 69 6e 63 6c 69 6e 65 | 64 20 74 6f 20 75 73 65 | incline|d to use|
|000020d0| 20 74 68 65 20 70 6f 70 | 75 6c 61 72 20 6d 65 74 | the pop|ular met|
|000020e0| 68 6f 64 2c 20 73 69 6e | 63 65 20 77 65 20 64 6f |hod, sin|ce we do|
|000020f0| 6e d5 74 20 63 61 72 65 | 20 74 6f 6f 20 6d 75 63 |n.t care| too muc|
|00002100| 68 20 61 62 6f 75 74 20 | 74 68 65 20 73 75 62 74 |h about |the subt|
|00002110| 6c 65 20 73 68 61 64 69 | 6e 67 20 65 66 66 65 63 |le shadi|ng effec|
|00002120| 74 73 20 6f 6e 20 74 68 | 65 20 6d 69 6e 75 74 65 |ts on th|e minute|
|00002130| 20 6d 61 72 6b 65 72 73 | 2e 20 48 6f 77 65 76 65 | markers|. Howeve|
|00002140| 72 2c 20 61 6e 20 61 72 | 74 69 73 74 20 6d 69 67 |r, an ar|tist mig|
|00002150| 68 74 20 62 65 20 6d 75 | 63 68 20 6d 6f 72 65 20 |ht be mu|ch more |
|00002160| 63 6f 6e 63 65 72 6e 65 | 64 20 77 69 74 68 20 74 |concerne|d with t|
|00002170| 68 65 20 0d 0d 4f 72 69 | 67 69 6e 61 6c 0d 20 20 |he ..Ori|ginal.  |
|00002180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00002190| 20 20 0d 09 44 65 66 61 | 75 6c 74 20 31 36 2d 63 |  ..Defa|ult 16-c|
|000021a0| 6f 6c 6f 72 20 70 61 6c | 65 74 74 65 20 09 31 36 |olor pal|ette .16|
|000021b0| 20 70 6f 70 75 6c 61 72 | 20 63 6f 6c 6f 72 73 0d | popular| colors.|
|000021c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|000021d0| 20 20 20 20 0d 09 31 36 | 20 6d 65 64 69 61 6e 20 |    ..16| median |
|000021e0| 63 6f 6c 6f 72 73 09 31 | 36 20 6f 63 74 72 65 65 |colors.1|6 octree|
|000021f0| 20 63 6f 6c 6f 72 73 0d | 46 69 67 75 72 65 20 31 | colors.|Figure 1|
|00002200| 0d 41 6e 20 49 6d 61 67 | 65 20 44 69 73 70 6c 61 |.An Imag|e Displa|
|00002210| 79 65 64 20 55 73 69 6e | 67 20 46 6f 75 72 20 44 |yed Usin|g Four D|
|00002220| 69 66 66 65 72 65 6e 74 | 20 43 6f 6c 6f 72 2d 50 |ifferent| Color-P|
|00002230| 69 63 6b 69 6e 67 20 4d | 65 74 68 6f 64 73 0d 0d |icking M|ethods..|
|00002240| 73 75 62 74 6c 65 20 73 | 68 61 64 69 6e 67 20 65 |subtle s|hading e|
|00002250| 66 66 65 63 74 73 20 61 | 6e 64 20 61 63 74 75 61 |ffects a|nd actua|
|00002260| 6c 6c 79 20 6e 6f 74 20 | 63 61 72 65 20 69 66 20 |lly not |care if |
|00002270| 74 68 65 20 66 61 63 65 | 20 6f 66 20 74 68 65 20 |the face| of the |
|00002280| 63 6c 6f 63 6b 20 77 65 | 6e 74 20 74 6f 20 61 20 |clock we|nt to a |
|00002290| 63 6f 6d 70 6c 65 74 65 | 6c 79 20 64 69 66 66 65 |complete|ly diffe|
|000022a0| 72 65 6e 74 20 62 75 74 | 20 73 74 69 6c 6c 20 73 |rent but| still s|
|000022b0| 6f 6c 69 64 20 73 68 61 | 64 65 2e 20 49 6e 20 74 |olid sha|de. In t|
|000022c0| 68 69 73 20 63 61 73 65 | 2c 20 74 68 65 20 61 72 |his case|, the ar|
|000022d0| 74 69 73 74 20 77 6f 75 | 6c 64 20 70 72 6f 62 61 |tist wou|ld proba|
|000022e0| 62 6c 79 20 70 69 63 6b | 20 74 68 65 20 6d 65 64 |bly pick| the med|
|000022f0| 69 61 6e 20 6f 72 20 6f | 63 74 72 65 65 20 6d 65 |ian or o|ctree me|
|00002300| 74 68 6f 64 2e 20 54 68 | 69 73 20 69 73 20 77 68 |thod. Th|is is wh|
|00002310| 79 20 61 70 70 6c 69 63 | 61 74 69 6f 6e 73 20 74 |y applic|ations t|
|00002320| 68 61 74 20 70 72 6f 76 | 69 64 65 20 63 6f 6c 6f |hat prov|ide colo|
|00002330| 72 20 6f 70 74 69 6d 69 | 7a 61 74 69 6f 6e 20 73 |r optimi|zation s|
|00002340| 68 6f 75 6c 64 20 61 6c | 6c 6f 77 20 74 68 65 20 |hould al|low the |
|00002350| 75 73 65 72 20 74 6f 20 | 63 68 6f 6f 73 65 20 62 |user to |choose b|
|00002360| 65 74 77 65 65 6e 20 74 | 68 65 20 76 61 72 69 6f |etween t|he vario|
|00002370| 75 73 20 61 76 61 69 6c | 61 62 6c 65 20 6d 65 74 |us avail|able met|
|00002380| 68 6f 64 73 2e 0d 54 68 | 65 72 65 20 69 73 20 61 |hods..Th|ere is a|
|00002390| 6c 73 6f 20 61 20 d2 73 | 79 73 74 65 6d d3 20 6d |lso a .s|ystem. m|
|000023a0| 65 74 68 6f 64 20 62 75 | 69 6c 74 20 69 6e 74 6f |ethod bu|ilt into|
|000023b0| 20 74 68 65 20 50 69 63 | 74 75 72 65 20 55 74 69 | the Pic|ture Uti|
|000023c0| 6c 69 74 69 65 73 20 50 | 61 63 6b 61 67 65 20 74 |lities P|ackage t|
|000023d0| 68 61 74 20 74 72 69 65 | 73 20 74 6f 20 73 65 6c |hat trie|s to sel|
|000023e0| 65 63 74 20 74 68 65 20 | 62 65 73 74 20 67 65 6e |ect the |best gen|
|000023f0| 65 72 61 6c 20 6d 65 74 | 68 6f 64 20 61 76 61 69 |eral met|hod avai|
|00002400| 6c 61 62 6c 65 2e 20 43 | 75 72 72 65 6e 74 6c 79 |lable. C|urrently|
|00002410| 2c 20 74 68 65 20 70 6f | 70 75 6c 61 72 20 6d 65 |, the po|pular me|
|00002420| 74 68 6f 64 20 69 73 20 | 73 65 6c 65 63 74 65 64 |thod is |selected|
|00002430| 20 69 66 20 74 68 65 20 | 6e 75 6d 62 65 72 20 6f | if the |number o|
|00002440| 66 20 72 65 71 75 65 73 | 74 65 64 20 63 6f 6c 6f |f reques|ted colo|
|00002450| 72 73 20 69 73 20 37 35 | 25 20 6f 72 20 67 72 65 |rs is 75|% or gre|
|00002460| 61 74 65 72 20 6f 66 20 | 74 68 65 20 74 6f 74 61 |ater of |the tota|
|00002470| 6c 20 6e 75 6d 62 65 72 | 20 6f 66 20 64 69 73 74 |l number| of dist|
|00002480| 69 6e 63 74 20 63 6f 6c | 6f 72 73 20 69 6e 20 74 |inct col|ors in t|
|00002490| 68 65 20 69 6d 61 67 65 | 20 28 74 6f 20 61 20 72 |he image| (to a r|
|000024a0| 65 73 6f 6c 75 74 69 6f | 6e 20 6f 66 20 66 69 76 |esolutio|n of fiv|
|000024b0| 65 20 62 69 74 73 20 70 | 65 72 20 63 6f 6c 6f 72 |e bits p|er color|
|000024c0| 20 63 6f 6d 70 6f 6e 65 | 6e 74 29 3b 20 6f 74 68 | compone|nt); oth|
|000024d0| 65 72 77 69 73 65 20 74 | 68 65 20 6d 65 64 69 61 |erwise t|he media|
|000024e0| 6e 20 6d 65 74 68 6f 64 | 20 69 73 20 73 65 6c 65 |n method| is sele|
|000024f0| 63 74 65 64 2e 20 54 68 | 65 20 6f 70 65 72 61 74 |cted. Th|e operat|
|00002500| 69 6f 6e 20 6f 66 20 74 | 68 69 73 20 73 79 73 74 |ion of t|his syst|
|00002510| 65 6d 20 6d 65 74 68 6f | 64 20 69 73 20 61 6c 6d |em metho|d is alm|
|00002520| 6f 73 74 20 63 65 72 74 | 61 69 6e 20 74 6f 20 63 |ost cert|ain to c|
|00002530| 68 61 6e 67 65 20 69 6e | 20 74 68 65 20 66 75 74 |hange in| the fut|
|00002540| 75 72 65 2e 0d 4e 6f 77 | 20 74 68 61 74 20 79 6f |ure..Now| that yo|
|00002550| 75 20 68 61 76 65 20 73 | 6f 6d 65 20 69 64 65 61 |u have s|ome idea|
|00002560| 20 6f 66 20 68 6f 77 20 | 74 68 65 20 61 76 61 69 | of how |the avai|
|00002570| 6c 61 62 6c 65 20 63 6f | 6c 6f 72 2d 70 69 63 6b |lable co|lor-pick|
|00002580| 69 6e 67 20 6d 65 74 68 | 6f 64 73 20 63 6f 6d 70 |ing meth|ods comp|
|00002590| 61 72 65 2c 20 77 65 20 | 74 75 72 6e 20 74 6f 20 |are, we |turn to |
|000025a0| 64 65 74 61 69 6c 73 20 | 6f 66 20 68 6f 77 20 74 |details |of how t|
|000025b0| 68 65 20 70 6f 70 75 6c | 61 72 2c 20 6d 65 64 69 |he popul|ar, medi|
|000025c0| 61 6e 2c 20 61 6e 64 20 | 6f 63 74 72 65 65 20 6d |an, and |octree m|
|000025d0| 65 74 68 6f 64 73 20 77 | 6f 72 6b 2e 0d 48 4f 57 |ethods w|ork..HOW|
|000025e0| 20 54 48 45 20 50 4f 50 | 55 4c 41 52 20 4d 45 54 | THE POP|ULAR MET|
|000025f0| 48 4f 44 20 57 4f 52 4b | 53 0d 54 68 65 20 70 6f |HOD WORK|S.The po|
|00002600| 70 75 6c 61 72 20 6d 65 | 74 68 6f 64 20 6f 66 20 |pular me|thod of |
|00002610| 63 6f 6c 6f 72 20 73 65 | 6c 65 63 74 69 6f 6e 20 |color se|lection |
|00002620| 69 73 20 74 68 65 20 65 | 61 73 69 65 73 74 20 74 |is the e|asiest t|
|00002630| 6f 20 75 6e 64 65 72 73 | 74 61 6e 64 20 61 6e 64 |o unders|tand and|
|00002640| 20 69 6e 20 67 65 6e 65 | 72 61 6c 20 70 72 6f 64 | in gene|ral prod|
|00002650| 75 63 65 73 20 74 68 65 | 20 6c 65 61 73 74 20 73 |uces the| least s|
|00002660| 61 74 69 73 66 61 63 74 | 6f 72 79 20 72 65 73 75 |atisfact|ory resu|
|00002670| 6c 74 73 2e 20 54 68 69 | 73 20 6d 65 74 68 6f 64 |lts. Thi|s method|
|00002680| 20 63 68 6f 6f 73 65 73 | 20 63 6f 6c 6f 72 73 20 | chooses| colors |
|00002690| 62 61 73 65 64 20 6f 6e | 20 68 6f 77 20 66 72 65 |based on| how fre|
|000026a0| 71 75 65 6e 74 6c 79 20 | 74 68 65 79 d5 72 65 20 |quently |they.re |
|000026b0| 75 73 65 64 20 69 6e 20 | 74 68 65 20 69 6d 61 67 |used in |the imag|
|000026c0| 65 2e 20 54 68 65 20 6f | 70 65 72 61 74 69 6f 6e |e. The o|peration|
|000026d0| 20 69 73 20 70 65 72 66 | 6f 72 6d 65 64 20 62 79 | is perf|ormed by|
|000026e0| 20 63 72 65 61 74 69 6e | 67 20 61 20 68 69 73 74 | creatin|g a hist|
|000026f0| 6f 67 72 61 6d 20 28 61 | 20 66 72 65 71 75 65 6e |ogram (a| frequen|
|00002700| 63 79 20 63 6f 75 6e 74 | 20 6f 66 20 65 61 63 68 |cy count| of each|
|00002710| 20 63 6f 6c 6f 72 29 20 | 61 6e 64 20 74 68 65 6e | color) |and then|
|00002720| 20 72 65 74 75 72 6e 69 | 6e 67 20 74 68 65 20 63 | returni|ng the c|
|00002730| 6f 6c 6f 72 73 20 74 68 | 61 74 20 6f 63 63 75 72 |olors th|at occur|
|00002740| 20 6d 6f 73 74 20 6f 66 | 74 65 6e 20 28 61 73 20 | most of|ten (as |
|00002750| 73 68 6f 77 6e 20 69 6e | 20 46 69 67 75 72 65 20 |shown in| Figure |
|00002760| 32 29 2c 20 75 70 20 74 | 6f 20 74 68 65 20 73 70 |2), up t|o the sp|
|00002770| 65 63 69 66 69 65 64 20 | 6e 75 6d 62 65 72 20 6f |ecified |number o|
|00002780| 66 20 63 6f 6c 6f 72 73 | 2e 20 49 66 20 74 68 65 |f colors|. If the|
|00002790| 20 69 6d 61 67 65 20 63 | 6f 6e 74 61 69 6e 73 20 | image c|ontains |
|000027a0| 6d 6f 72 65 20 74 68 61 | 6e 20 32 35 36 20 64 69 |more tha|n 256 di|
|000027b0| 66 66 65 72 65 6e 74 20 | 63 6f 6c 6f 72 73 20 6f |fferent |colors o|
|000027c0| 72 20 69 66 20 61 6e 79 | 20 6f 66 20 74 68 65 20 |r if any| of the |
|000027d0| 73 6f 75 72 63 65 20 69 | 74 65 6d 73 20 61 72 65 |source i|tems are|
|000027e0| 20 33 32 2d 62 69 74 20 | 70 69 78 4d 61 70 73 2c | 32-bit |pixMaps,|
|000027f0| 20 50 69 63 74 75 72 65 | 20 55 74 69 6c 69 74 69 | Picture| Utiliti|
|00002800| 65 73 20 6f 6e 6c 79 20 | 6d 61 69 6e 74 61 69 6e |es only |maintain|
|00002810| 73 20 63 6f 6c 6f 72 20 | 69 6e 66 6f 72 6d 61 74 |s color |informat|
|00002820| 69 6f 6e 20 74 6f 20 61 | 20 72 65 73 6f 6c 75 74 |ion to a| resolut|
|00002830| 69 6f 6e 20 6f 66 20 66 | 69 76 65 20 62 69 74 73 |ion of f|ive bits|
|00002840| 20 70 65 72 20 63 6f 6c | 6f 72 20 63 6f 6d 70 6f | per col|or compo|
|00002850| 6e 65 6e 74 2e 20 54 68 | 75 73 2c 20 63 6f 6c 6f |nent. Th|us, colo|
|00002860| 72 73 20 6d 75 73 74 20 | 64 69 66 66 65 72 20 69 |rs must |differ i|
|00002870| 6e 20 74 68 65 20 68 69 | 67 68 65 73 74 20 66 69 |n the hi|ghest fi|
|00002880| 76 65 20 62 69 74 73 20 | 6f 66 20 61 6e 79 20 6f |ve bits |of any o|
|00002890| 66 20 74 68 65 20 74 68 | 72 65 65 20 63 6f 6c 6f |f the th|ree colo|
|000028a0| 72 20 63 6f 6d 70 6f 6e | 65 6e 74 73 20 28 72 65 |r compon|ents (re|
|000028b0| 64 2c 20 67 72 65 65 6e | 2c 20 61 6e 64 20 62 6c |d, green|, and bl|
|000028c0| 75 65 29 20 74 6f 20 62 | 65 20 63 6f 6e 73 69 64 |ue) to b|e consid|
|000028d0| 65 72 65 64 20 64 69 73 | 74 69 6e 63 74 2e 0d 46 |ered dis|tinct..F|
|000028e0| 69 67 75 72 65 20 32 0d | 50 69 63 6b 69 6e 67 20 |igure 2.|Picking |
|000028f0| 46 6f 75 72 20 43 6f 6c | 6f 72 73 20 55 73 69 6e |Four Col|ors Usin|
|00002900| 67 20 74 68 65 20 50 6f | 70 75 6c 61 72 20 4d 65 |g the Po|pular Me|
|00002910| 74 68 6f 64 0d 49 6e 20 | 46 69 67 75 72 65 20 32 |thod.In |Figure 2|
|00002920| 2c 20 74 68 65 20 78 2d | 61 78 69 73 20 72 65 70 |, the x-|axis rep|
|00002930| 72 65 73 65 6e 74 73 20 | 65 61 63 68 20 70 6f 73 |resents |each pos|
|00002940| 73 69 62 6c 65 20 52 47 | 42 20 63 6f 6c 6f 72 20 |sible RG|B color |
|00002950| 74 6f 20 61 20 72 65 73 | 6f 6c 75 74 69 6f 6e 20 |to a res|olution |
|00002960| 6f 66 20 66 69 76 65 20 | 62 69 74 73 20 70 65 72 |of five |bits per|
|00002970| 20 63 6f 6d 70 6f 6e 65 | 6e 74 2e 20 54 68 65 73 | compone|nt. Thes|
|00002980| 65 20 63 6f 6c 6f 72 73 | 20 72 61 6e 67 65 20 66 |e colors| range f|
|00002990| 72 6f 6d 20 30 2d 30 2d | 30 20 28 30 20 72 65 64 |rom 0-0-|0 (0 red|
|000029a0| 2c 20 30 20 67 72 65 65 | 6e 2c 20 30 20 62 6c 75 |, 0 gree|n, 0 blu|
|000029b0| 65 29 20 74 6f 20 33 32 | 2d 33 32 2d 33 32 20 28 |e) to 32|-32-32 (|
|000029c0| 33 32 20 72 65 64 2c 20 | 33 32 20 67 72 65 65 6e |32 red, |32 green|
|000029d0| 2c 20 33 32 20 62 6c 75 | 65 29 20 69 6e 20 74 68 |, 32 blu|e) in th|
|000029e0| 65 20 68 69 67 68 20 66 | 69 76 65 20 62 69 74 73 |e high f|ive bits|
|000029f0| 20 6f 66 20 74 68 65 20 | 72 65 64 2d 67 72 65 65 | of the |red-gree|
|00002a00| 6e 2d 62 6c 75 65 20 63 | 6f 6c 6f 72 20 63 6f 6d |n-blue c|olor com|
|00002a10| 70 6f 6e 65 6e 74 73 2c | 20 66 6f 72 20 61 20 74 |ponents,| for a t|
|00002a20| 6f 74 61 6c 20 6f 66 20 | 32 31 35 20 6f 72 20 61 |otal of |215 or a|
|00002a30| 72 6f 75 6e 64 20 33 32 | 2c 30 30 30 20 65 6e 74 |round 32|,000 ent|
|00002a40| 72 69 65 73 2e 20 54 68 | 65 20 79 2d 61 78 69 73 |ries. Th|e y-axis|
|00002a50| 20 6d 65 61 73 75 72 65 | 73 20 74 68 65 20 66 72 | measure|s the fr|
|00002a60| 65 71 75 65 6e 63 79 20 | 6f 66 20 65 61 63 68 20 |equency |of each |
|00002a70| 6f 66 20 74 68 65 20 63 | 6f 6c 6f 72 73 2c 20 75 |of the c|olors, u|
|00002a80| 70 20 74 6f 20 61 20 6d | 61 78 69 6d 75 6d 20 6f |p to a m|aximum o|
|00002a90| 66 20 33 32 2c 37 36 37 | 20 6f 63 63 75 72 72 65 |f 32,767| occurre|
|00002aa0| 6e 63 65 73 2e 20 54 68 | 75 73 2c 20 74 68 69 73 |nces. Th|us, this|
|00002ab0| 20 74 61 62 6c 65 20 63 | 6f 6e 74 61 69 6e 73 20 | table c|ontains |
|00002ac0| 32 31 35 20 65 6e 74 72 | 69 65 73 20 6f 66 20 6f |215 entr|ies of o|
|00002ad0| 6e 65 20 77 6f 72 64 20 | 65 61 63 68 20 61 6e 64 |ne word |each and|
|00002ae0| 20 6f 63 63 75 70 69 65 | 73 20 36 34 4b 20 6f 66 | occupie|s 64K of|
|00002af0| 20 6d 65 6d 6f 72 79 2e | 0d 46 6f 72 20 63 75 73 | memory.|.For cus|
|00002b00| 74 6f 6d 20 6d 65 74 68 | 6f 64 73 2c 20 50 69 63 |tom meth|ods, Pic|
|00002b10| 74 75 72 65 20 55 74 69 | 6c 69 74 69 65 73 20 63 |ture Uti|lities c|
|00002b20| 61 6e 20 67 65 6e 65 72 | 61 74 65 20 74 68 69 73 |an gener|ate this|
|00002b30| 20 68 69 73 74 6f 67 72 | 61 6d 20 6f 66 20 63 6f | histogr|am of co|
|00002b40| 6c 6f 72 20 75 73 61 67 | 65 20 66 6f 72 20 79 6f |lor usag|e for yo|
|00002b50| 75 2e 20 49 66 20 79 6f | 75 72 20 63 75 73 74 6f |u. If yo|ur custo|
|00002b60| 6d 20 6d 65 74 68 6f 64 | 20 77 61 6e 74 73 20 74 |m method| wants t|
|00002b70| 68 69 73 2c 20 69 74 73 | 20 69 6e 69 74 69 61 6c |his, its| initial|
|00002b80| 69 7a 61 74 69 6f 6e 20 | 73 75 62 72 6f 75 74 69 |ization |subrouti|
|00002b90| 6e 65 20 6d 75 73 74 20 | 72 65 74 75 72 6e 20 74 |ne must |return t|
|00002ba0| 68 65 20 76 61 6c 75 65 | 20 43 6f 6c 6f 72 42 61 |he value| ColorBa|
|00002bb0| 6e 6b 49 73 35 35 35 20 | 66 6f 72 20 74 68 65 20 |nkIs555 |for the |
|00002bc0| 63 6f 6c 6f 72 20 62 61 | 6e 6b 20 70 61 72 61 6d |color ba|nk param|
|00002bd0| 65 74 65 72 2e 20 54 68 | 65 20 6f 63 74 72 65 65 |eter. Th|e octree|
|00002be0| 20 6d 65 74 68 6f 64 20 | 64 65 73 63 72 69 62 65 | method |describe|
|00002bf0| 64 20 6c 61 74 65 72 20 | 69 6e 20 74 68 69 73 20 |d later |in this |
|00002c00| 61 72 74 69 63 6c 65 20 | 64 6f 65 73 20 6e 6f 74 |article |does not|
|00002c10| 20 75 73 65 20 61 20 68 | 69 73 74 6f 67 72 61 6d | use a h|istogram|
|00002c20| 2e 20 49 6e 73 74 65 61 | 64 2c 20 69 74 20 75 73 |. Instea|d, it us|
|00002c30| 65 73 20 69 74 73 20 6f | 77 6e 20 63 75 73 74 6f |es its o|wn custo|
|00002c40| 6d 20 63 6f 6c 6f 72 20 | 62 61 6e 6b 20 61 6e 64 |m color |bank and|
|00002c50| 20 74 68 75 73 20 72 65 | 74 75 72 6e 73 20 43 6f | thus re|turns Co|
|00002c60| 6c 6f 72 42 61 6e 6b 49 | 73 43 75 73 74 6f 6d 20 |lorBankI|sCustom |
|00002c70| 61 73 20 69 74 73 20 63 | 6f 6c 6f 72 20 62 61 6e |as its c|olor ban|
|00002c80| 6b 20 70 61 72 61 6d 65 | 74 65 72 2e 0d 48 4f 57 |k parame|ter..HOW|
|00002c90| 20 54 48 45 20 4d 45 44 | 49 41 4e 20 4d 45 54 48 | THE MED|IAN METH|
|00002ca0| 4f 44 20 57 4f 52 4b 53 | 0d 54 68 65 20 6d 65 64 |OD WORKS|.The med|
|00002cb0| 69 61 6e 20 6d 65 74 68 | 6f 64 20 69 73 20 61 6e |ian meth|od is an|
|00002cc0| 20 69 74 65 72 61 74 69 | 76 65 20 61 6c 67 6f 72 | iterati|ve algor|
|00002cd0| 69 74 68 6d 20 74 68 61 | 74 20 76 69 65 77 73 20 |ithm tha|t views |
|00002ce0| 74 68 65 20 63 6f 6c 6f | 72 73 20 69 6e 20 61 6e |the colo|rs in an|
|00002cf0| 20 69 6d 61 67 65 20 61 | 73 20 69 66 20 74 68 65 | image a|s if the|
|00002d00| 79 20 77 65 72 65 20 61 | 72 72 61 6e 67 65 64 20 |y were a|rranged |
|00002d10| 69 6e 20 61 20 63 75 62 | 65 20 77 69 74 68 20 61 |in a cub|e with a|
|00002d20| 78 65 73 20 72 65 70 72 | 65 73 65 6e 74 69 6e 67 |xes repr|esenting|
|00002d30| 20 74 68 65 20 72 65 64 | 2c 20 67 72 65 65 6e 2c | the red|, green,|
|00002d40| 20 61 6e 64 20 62 6c 75 | 65 20 63 6f 6d 70 6f 6e | and blu|e compon|
|00002d50| 65 6e 74 73 2e 20 49 74 | 20 73 74 61 72 74 73 20 |ents. It| starts |
|00002d60| 62 79 20 67 65 6e 65 72 | 61 74 69 6e 67 20 61 20 |by gener|ating a |
|00002d70| 68 69 73 74 6f 67 72 61 | 6d 20 6f 66 20 74 68 65 |histogra|m of the|
|00002d80| 20 73 6f 75 72 63 65 20 | 63 6f 6c 6f 72 73 2c 20 | source |colors, |
|00002d90| 6a 75 73 74 20 61 73 20 | 74 68 65 20 70 6f 70 75 |just as |the popu|
|00002da0| 6c 61 72 20 6d 65 74 68 | 6f 64 20 64 6f 65 73 2e |lar meth|od does.|
|00002db0| 20 48 6f 77 65 76 65 72 | 2c 20 77 68 69 6c 65 20 | However|, while |
|00002dc0| 74 68 65 20 70 6f 70 75 | 6c 61 72 20 6d 65 74 68 |the popu|lar meth|
|00002dd0| 6f 64 20 69 73 20 70 72 | 65 74 74 79 20 6d 75 63 |od is pr|etty muc|
|00002de0| 68 20 64 6f 6e 65 20 61 | 66 74 65 72 20 74 68 69 |h done a|fter thi|
|00002df0| 73 2c 20 74 68 65 20 6d | 65 64 69 61 6e 20 6d 65 |s, the m|edian me|
|00002e00| 74 68 6f 64 d5 73 20 72 | 65 61 6c 20 77 6f 72 6b |thod.s r|eal work|
|00002e10| 20 68 61 73 20 6f 6e 6c | 79 20 6a 75 73 74 20 62 | has onl|y just b|
|00002e20| 65 67 75 6e 2e 0d 54 68 | 65 20 66 69 72 73 74 20 |egun..Th|e first |
|00002e30| 72 65 61 6c 20 73 74 65 | 70 20 69 73 20 74 6f 20 |real ste|p is to |
|00002e40| 64 65 74 65 72 6d 69 6e | 65 20 74 68 65 20 73 6d |determin|e the sm|
|00002e50| 61 6c 6c 65 73 74 20 52 | 47 42 20 63 75 62 65 20 |allest R|GB cube |
|00002e60| 74 68 61 74 20 77 69 6c | 6c 20 68 6f 6c 64 20 61 |that wil|l hold a|
|00002e70| 6c 6c 20 74 68 65 20 63 | 6f 6c 6f 72 73 20 69 6e |ll the c|olors in|
|00002e80| 20 74 68 65 20 69 6d 61 | 67 65 2e 20 41 66 74 65 | the ima|ge. Afte|
|00002e90| 72 20 66 69 6e 64 69 6e | 67 20 74 68 65 20 6d 65 |r findin|g the me|
|00002ea0| 64 69 61 6e 20 63 6f 6c | 6f 72 20 61 6c 6f 6e 67 |dian col|or along|
|00002eb0| 20 74 68 65 20 6c 6f 6e | 67 65 73 74 20 63 6f 6c | the lon|gest col|
|00002ec0| 6f 72 20 61 78 69 73 2c | 20 69 74 20 74 68 65 6e |or axis,| it then|
|00002ed0| 20 70 75 74 73 20 61 6c | 6c 20 74 68 65 20 63 6f | puts al|l the co|
|00002ee0| 6c 6f 72 73 20 6f 6e 20 | 6f 6e 65 20 73 69 64 65 |lors on |one side|
|00002ef0| 20 6f 66 20 74 68 61 74 | 20 63 6f 6c 6f 72 20 69 | of that| color i|
|00002f00| 6e 74 6f 20 6f 6e 65 20 | 62 6f 78 20 61 6e 64 20 |nto one |box and |
|00002f10| 74 68 65 20 72 65 6d 61 | 69 6e 69 6e 67 20 63 6f |the rema|ining co|
|00002f20| 6c 6f 72 73 20 69 6e 74 | 6f 20 61 6e 6f 74 68 65 |lors int|o anothe|
|00002f30| 72 20 62 6f 78 2e 20 49 | 74 20 63 6f 6e 74 69 6e |r box. I|t contin|
|00002f40| 75 65 73 20 74 68 69 73 | 20 6d 65 61 73 75 72 69 |ues this| measuri|
|00002f50| 6e 67 20 61 6e 64 20 73 | 70 6c 69 74 74 69 6e 67 |ng and s|plitting|
|00002f60| 20 70 72 6f 63 65 73 73 | 20 75 6e 74 69 6c 20 74 | process| until t|
|00002f70| 68 65 20 63 6f 6c 6f 72 | 73 20 68 61 76 65 20 62 |he color|s have b|
|00002f80| 65 65 6e 20 61 73 73 69 | 67 6e 65 64 20 74 6f 20 |een assi|gned to |
|00002f90| 61 73 20 6d 61 6e 79 20 | 62 6f 78 65 73 20 61 73 |as many |boxes as|
|00002fa0| 20 63 6f 6c 6f 72 73 20 | 72 65 71 75 65 73 74 65 | colors |requeste|
|00002fb0| 64 2e 20 54 68 65 6e 20 | 74 68 65 20 77 65 69 67 |d. Then |the weig|
|00002fc0| 68 74 65 64 20 61 76 65 | 72 61 67 65 20 63 6f 6c |hted ave|rage col|
|00002fd0| 6f 72 20 6f 66 20 65 61 | 63 68 20 6f 66 20 74 68 |or of ea|ch of th|
|00002fe0| 65 20 62 6f 78 65 73 20 | 69 73 20 72 65 74 75 72 |e boxes |is retur|
|00002ff0| 6e 65 64 20 61 73 20 74 | 68 65 20 63 6f 6c 6f 72 |ned as t|he color|
|00003000| 20 73 65 74 20 74 6f 20 | 75 73 65 2e 0d 53 69 6e | set to |use..Sin|
|00003010| 63 65 20 74 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |ce the a|lgorithm|
|00003020| 20 69 73 20 6d 75 63 68 | 20 65 61 73 69 65 72 20 | is much| easier |
|00003030| 74 6f 20 76 69 73 75 61 | 6c 69 7a 65 20 69 6e 20 |to visua|lize in |
|00003040| 74 77 6f 20 64 69 6d 65 | 6e 73 69 6f 6e 73 2c 20 |two dime|nsions, |
|00003050| 77 65 d5 6c 6c 20 69 6c | 6c 75 73 74 72 61 74 65 |we.ll il|lustrate|
|00003060| 20 68 6f 77 20 69 74 20 | 77 6f 72 6b 73 20 69 6e | how it |works in|
|00003070| 20 74 68 65 20 72 65 64 | 2d 67 72 65 65 6e 20 70 | the red|-green p|
|00003080| 6c 61 6e 65 20 6f 6e 6c | 79 2e 20 45 78 74 65 6e |lane onl|y. Exten|
|00003090| 64 69 6e 67 20 74 68 65 | 20 61 6c 67 6f 72 69 74 |ding the| algorit|
|000030a0| 68 6d 20 74 6f 20 74 68 | 72 65 65 20 64 69 6d 65 |hm to th|ree dime|
|000030b0| 6e 73 69 6f 6e 73 20 69 | 73 20 73 74 72 61 69 67 |nsions i|s straig|
|000030c0| 68 74 66 6f 72 77 61 72 | 64 2e 20 49 6e 20 46 69 |htforwar|d. In Fi|
|000030d0| 67 75 72 65 20 33 2c 20 | 65 69 67 68 74 20 63 6f |gure 3, |eight co|
|000030e0| 6c 6f 72 73 20 61 72 65 | 20 70 72 65 73 65 6e 74 |lors are| present|
|000030f0| 20 69 6e 20 74 68 65 20 | 72 65 64 2d 67 72 65 65 | in the |red-gree|
|00003100| 6e 20 63 6f 6c 6f 72 20 | 70 6c 61 6e 65 20 28 74 |n color |plane (t|
|00003110| 68 65 20 62 6c 75 65 20 | 63 6f 6d 70 6f 6e 65 6e |he blue |componen|
|00003120| 74 20 69 73 20 74 61 6b | 65 6e 20 61 73 20 30 20 |t is tak|en as 0 |
|00003130| 66 6f 72 20 61 6c 6c 20 | 63 6f 6c 6f 72 73 29 2e |for all |colors).|
|00003140| 20 49 6e 20 74 68 69 73 | 20 73 69 6d 70 6c 69 66 | In this| simplif|
|00003150| 69 65 64 20 65 78 61 6d | 70 6c 65 2c 20 65 61 63 |ied exam|ple, eac|
|00003160| 68 20 63 6f 6c 6f 72 20 | 6f 63 63 75 72 73 20 6f |h color |occurs o|
|00003170| 6e 6c 79 20 6f 6e 63 65 | 2e 20 49 6e 20 74 68 65 |nly once|. In the|
|00003180| 20 67 65 6e 65 72 61 6c | 20 63 61 73 65 2c 20 69 | general| case, i|
|00003190| 66 20 61 20 63 6f 6c 6f | 72 20 6f 63 63 75 72 73 |f a colo|r occurs|
|000031a0| 20 6d 6f 72 65 20 74 68 | 61 6e 20 6f 6e 63 65 2c | more th|an once,|
|000031b0| 20 74 68 61 74 20 63 6f | 6c 6f 72 20 69 73 20 77 | that co|lor is w|
|000031c0| 65 69 67 68 74 65 64 20 | 61 63 63 6f 72 64 69 6e |eighted |accordin|
|000031d0| 67 6c 79 20 69 6e 20 74 | 68 65 20 66 69 6e 61 6c |gly in t|he final|
|000031e0| 20 73 74 65 70 20 77 68 | 65 6e 20 74 68 65 20 63 | step wh|en the c|
|000031f0| 6f 6c 6f 72 73 20 69 6e | 20 65 61 63 68 20 62 6f |olors in| each bo|
|00003200| 78 20 61 72 65 20 61 76 | 65 72 61 67 65 64 2e 0d |x are av|eraged..|
|00003210| 54 68 65 20 66 69 72 73 | 74 20 64 69 76 69 73 69 |The firs|t divisi|
|00003220| 6f 6e 20 69 73 20 61 6c | 6f 6e 67 20 74 68 65 20 |on is al|ong the |
|00003230| 67 72 65 65 6e 20 61 78 | 69 73 20 73 69 6e 63 65 |green ax|is since|
|00003240| 20 74 68 65 20 64 69 66 | 66 65 72 65 6e 63 65 20 | the dif|ference |
|00003250| 62 65 74 77 65 65 6e 20 | 74 68 65 20 6d 6f 73 74 |between |the most|
|00003260| 20 67 72 65 65 6e 20 61 | 6e 64 20 74 68 65 20 6c | green a|nd the l|
|00003270| 65 61 73 74 20 67 72 65 | 65 6e 20 63 6f 6c 6f 72 |east gre|en color|
|00003280| 20 69 73 20 73 6c 69 67 | 68 74 6c 79 20 6c 61 72 | is slig|htly lar|
|00003290| 67 65 72 20 74 68 61 6e | 20 74 68 65 20 64 69 66 |ger than| the dif|
|000032a0| 66 65 72 65 6e 63 65 20 | 62 65 74 77 65 65 6e 20 |ference |between |
|000032b0| 74 68 65 20 6d 6f 73 74 | 20 72 65 64 20 61 6e 64 |the most| red and|
|000032c0| 20 74 68 65 20 6c 65 61 | 73 74 20 72 65 64 20 63 | the lea|st red c|
|000032d0| 6f 6c 6f 72 2e 20 54 68 | 69 73 20 64 69 76 69 73 |olor. Th|is divis|
|000032e0| 69 6f 6e 20 72 65 73 75 | 6c 74 73 20 69 6e 20 74 |ion resu|lts in t|
|000032f0| 68 65 20 74 77 6f 20 62 | 6f 78 65 73 20 73 68 6f |he two b|oxes sho|
|00003300| 77 6e 20 69 6e 20 73 74 | 65 70 20 32 20 6f 66 20 |wn in st|ep 2 of |
|00003310| 46 69 67 75 72 65 20 33 | 2e 20 54 68 65 20 6c 61 |Figure 3|. The la|
|00003320| 72 67 65 73 74 20 64 69 | 66 66 65 72 65 6e 63 65 |rgest di|fference|
|00003330| 20 69 6e 20 63 6f 6c 6f | 72 73 20 61 6c 6f 6e 67 | in colo|rs along|
|00003340| 20 6f 6e 65 20 61 78 69 | 73 20 69 73 20 6e 6f 77 | one axi|s is now|
|00003350| 20 61 6c 6f 6e 67 20 74 | 68 65 20 72 65 64 20 61 | along t|he red a|
|00003360| 78 69 73 20 6f 66 20 74 | 68 65 20 74 6f 70 20 62 |xis of t|he top b|
|00003370| 6f 78 2e 20 54 68 75 73 | 2c 20 74 68 69 73 20 62 |ox. Thus|, this b|
|00003380| 6f 78 20 69 73 20 64 69 | 76 69 64 65 64 20 69 6e |ox is di|vided in|
|00003390| 74 6f 20 74 77 6f 20 61 | 6c 6f 6e 67 20 74 68 65 |to two a|long the|
|000033a0| 20 72 65 64 20 61 78 69 | 73 2c 20 6c 65 61 76 69 | red axi|s, leavi|
|000033b0| 6e 67 20 75 73 20 77 69 | 74 68 20 74 68 72 65 65 |ng us wi|th three|
|000033c0| 20 62 6f 78 65 73 20 61 | 73 20 73 68 6f 77 6e 20 | boxes a|s shown |
|000033d0| 69 6e 20 73 74 65 70 20 | 33 2e 20 54 68 69 73 20 |in step |3. This |
|000033e0| 74 69 6d 65 20 74 68 65 | 20 6c 61 72 67 65 73 74 |time the| largest|
|000033f0| 20 64 69 66 66 65 72 65 | 6e 63 65 20 69 73 20 69 | differe|nce is i|
|00003400| 6e 20 74 68 65 20 72 65 | 64 20 61 78 69 73 20 6f |n the re|d axis o|
|00003410| 66 20 74 68 65 20 62 6f | 74 74 6f 6d 20 62 6f 78 |f the bo|ttom box|
|00003420| 2c 20 73 6f 20 74 68 69 | 73 20 62 6f 78 20 69 73 |, so thi|s box is|
|00003430| 20 64 69 76 69 64 65 64 | 20 61 6c 6f 6e 67 20 74 | divided| along t|
|00003440| 68 65 20 6d 65 64 69 61 | 6e 2c 20 70 72 6f 64 75 |he media|n, produ|
|00003450| 63 69 6e 67 20 74 68 65 | 20 72 65 73 75 6c 74 20 |cing the| result |
|00003460| 73 68 6f 77 6e 20 69 6e | 20 73 74 65 70 20 34 2e |shown in| step 4.|
|00003470| 0d 0d 46 69 67 75 72 65 | 20 33 0d 50 69 63 6b 69 |..Figure| 3.Picki|
|00003480| 6e 67 20 46 6f 75 72 20 | 43 6f 6c 6f 72 73 20 55 |ng Four |Colors U|
|00003490| 73 69 6e 67 20 74 68 65 | 20 4d 65 64 69 61 6e 20 |sing the| Median |
|000034a0| 4d 65 74 68 6f 64 0d 57 | 65 20 6e 6f 77 20 68 61 |Method.W|e now ha|
|000034b0| 76 65 20 66 6f 75 72 20 | 62 6f 78 65 73 2c 20 61 |ve four |boxes, a|
|000034c0| 6e 64 20 73 69 6e 63 65 | 20 74 68 65 20 62 65 73 |nd since| the bes|
|000034d0| 74 20 66 6f 75 72 20 63 | 6f 6c 6f 72 73 20 77 65 |t four c|olors we|
|000034e0| 72 65 20 72 65 71 75 65 | 73 74 65 64 20 69 6e 20 |re reque|sted in |
|000034f0| 74 68 69 73 20 65 78 61 | 6d 70 6c 65 2c 20 77 65 |this exa|mple, we|
|00003500| d5 72 65 20 64 6f 6e 65 | 2e 20 54 68 65 20 63 6f |.re done|. The co|
|00003510| 6c 6f 72 73 20 72 65 74 | 75 72 6e 65 64 20 61 72 |lors ret|urned ar|
|00003520| 65 20 74 68 65 20 77 65 | 69 67 68 74 65 64 20 61 |e the we|ighted a|
|00003530| 76 65 72 61 67 65 73 20 | 6f 66 20 74 68 65 20 63 |verages |of the c|
|00003540| 6f 6c 6f 72 73 20 69 6e | 20 65 61 63 68 20 6f 66 |olors in| each of|
|00003550| 20 74 68 65 20 62 6f 78 | 65 73 2c 20 61 73 20 73 | the box|es, as s|
|00003560| 68 6f 77 6e 2e 2e 0d 48 | 4f 57 20 54 48 45 20 4f |hown...H|OW THE O|
|00003570| 43 54 52 45 45 20 4d 45 | 54 48 4f 44 20 57 4f 52 |CTREE ME|THOD WOR|
|00003580| 4b 53 0d 54 68 65 20 6f | 63 74 72 65 65 20 6d 65 |KS.The o|ctree me|
|00003590| 74 68 6f 64 2c 20 6c 69 | 6b 65 20 74 68 65 20 6d |thod, li|ke the m|
|000035a0| 65 64 69 61 6e 20 6d 65 | 74 68 6f 64 2c 20 69 73 |edian me|thod, is|
|000035b0| 20 61 6e 20 69 74 65 72 | 61 74 69 76 65 20 61 6c | an iter|ative al|
|000035c0| 67 6f 72 69 74 68 6d 20 | 74 68 61 74 20 64 65 73 |gorithm |that des|
|000035d0| 63 72 69 62 65 73 20 68 | 6f 77 20 74 68 65 20 63 |cribes h|ow the c|
|000035e0| 6f 6c 6f 72 73 20 69 6e | 20 61 6e 20 69 6d 61 67 |olors in| an imag|
|000035f0| 65 20 61 72 65 20 61 72 | 72 61 6e 67 65 64 20 69 |e are ar|ranged i|
|00003600| 6e 20 61 6e 20 52 47 42 | 20 63 75 62 65 2e 20 4c |n an RGB| cube. L|
|00003610| 69 6b 65 20 74 68 65 20 | 6d 65 64 69 61 6e 20 6d |ike the |median m|
|00003620| 65 74 68 6f 64 2c 20 74 | 68 65 20 6f 63 74 72 65 |ethod, t|he octre|
|00003630| 65 20 6d 65 74 68 6f 64 | 20 67 72 6f 75 70 73 20 |e method| groups |
|00003640| 74 68 65 20 63 6f 6c 6f | 72 73 20 69 6e 20 61 6e |the colo|rs in an|
|00003650| 20 69 6d 61 67 65 20 74 | 6f 67 65 74 68 65 72 20 | image t|ogether |
|00003660| 69 6e 74 6f 20 74 68 65 | 20 73 61 6d 65 20 6e 75 |into the| same nu|
|00003670| 6d 62 65 72 20 6f 66 20 | 62 6f 78 65 73 20 61 73 |mber of |boxes as|
|00003680| 20 63 6f 6c 6f 72 73 20 | 72 65 71 75 65 73 74 65 | colors |requeste|
|00003690| 64 20 61 6e 64 20 74 68 | 65 6e 20 72 65 74 75 72 |d and th|en retur|
|000036a0| 6e 73 20 77 65 69 67 68 | 74 65 64 20 61 76 65 72 |ns weigh|ted aver|
|000036b0| 61 67 65 73 20 66 72 6f | 6d 20 74 68 65 73 65 20 |ages fro|m these |
|000036c0| 62 6f 78 65 73 2c 20 62 | 75 74 20 74 68 65 20 77 |boxes, b|ut the w|
|000036d0| 61 79 20 74 68 65 73 65 | 20 62 6f 78 65 73 20 61 |ay these| boxes a|
|000036e0| 72 65 20 63 6f 6e 73 74 | 72 75 63 74 65 64 20 64 |re const|ructed d|
|000036f0| 69 66 66 65 72 73 20 73 | 75 62 73 74 61 6e 74 69 |iffers s|ubstanti|
|00003700| 61 6c 6c 79 20 62 65 74 | 77 65 65 6e 20 74 68 65 |ally bet|ween the|
|00003710| 20 74 77 6f 20 6d 65 74 | 68 6f 64 73 2e 0d 0d 57 | two met|hods...W|
|00003720| 68 69 6c 65 20 74 68 65 | 20 70 6f 70 75 6c 61 72 |hile the| popular|
|00003730| 20 61 6e 64 20 6d 65 64 | 69 61 6e 20 6d 65 74 68 | and med|ian meth|
|00003740| 6f 64 73 20 70 72 6f 63 | 65 73 73 20 64 61 74 61 |ods proc|ess data|
|00003750| 20 74 68 61 74 d5 73 20 | 73 74 6f 72 65 64 20 69 | that.s |stored i|
|00003760| 6e 20 61 20 68 69 73 74 | 6f 67 72 61 6d 2c 20 74 |n a hist|ogram, t|
|00003770| 68 65 20 6f 63 74 72 65 | 65 20 6d 65 74 68 6f 64 |he octre|e method|
|00003780| 20 64 6f 65 73 20 69 74 | 73 20 63 6f 6c 6f 72 20 | does it|s color |
|00003790| 61 63 63 6f 75 6e 74 69 | 6e 67 20 76 69 61 20 61 |accounti|ng via a|
|000037a0| 20 74 72 65 65 2e 20 54 | 68 69 73 20 6d 65 61 6e | tree. T|his mean|
|000037b0| 73 20 74 68 61 74 20 72 | 61 74 68 65 72 20 74 68 |s that r|ather th|
|000037c0| 61 6e 20 74 72 75 6e 63 | 61 74 69 6e 67 20 63 6f |an trunc|ating co|
|000037d0| 6c 6f 72 73 20 74 6f 20 | 35 2d 35 2d 35 20 66 72 |lors to |5-5-5 fr|
|000037e0| 6f 6d 20 74 68 65 20 67 | 65 74 2d 67 6f 2c 20 74 |om the g|et-go, t|
|000037f0| 68 65 20 6d 65 74 68 6f | 64 20 6d 61 69 6e 74 61 |he metho|d mainta|
|00003800| 69 6e 73 20 74 68 65 20 | 66 75 6c 6c 20 38 2d 38 |ins the |full 8-8|
|00003810| 2d 38 20 63 6f 6c 6f 72 | 20 74 68 72 6f 75 67 68 |-8 color| through|
|00003820| 6f 75 74 20 74 68 65 20 | 70 72 6f 63 65 73 73 2e |out the |process.|
|00003830| 0d 41 6e 20 6f 63 74 72 | 65 65 20 69 73 20 73 69 |.An octr|ee is si|
|00003840| 6d 69 6c 61 72 20 74 6f | 20 61 20 62 69 6e 61 72 |milar to| a binar|
|00003850| 79 20 74 72 65 65 2c 20 | 65 78 63 65 70 74 20 74 |y tree, |except t|
|00003860| 68 61 74 20 69 6e 73 74 | 65 61 64 20 6f 66 20 68 |hat inst|ead of h|
|00003870| 61 76 69 6e 67 20 74 77 | 6f 20 62 72 61 6e 63 68 |aving tw|o branch|
|00003880| 65 73 20 61 74 20 65 61 | 63 68 20 6e 6f 64 65 2c |es at ea|ch node,|
|00003890| 20 69 74 20 68 61 73 20 | 65 69 67 68 74 2e 20 41 | it has |eight. A|
|000038a0| 6e 20 6f 63 74 72 65 65 | 20 63 6f 72 72 65 73 70 |n octree| corresp|
|000038b0| 6f 6e 64 73 20 74 6f 20 | 61 20 63 75 62 65 20 77 |onds to |a cube w|
|000038c0| 69 74 68 20 61 78 65 73 | 20 72 65 70 72 65 73 65 |ith axes| represe|
|000038d0| 6e 74 69 6e 67 20 74 68 | 65 20 72 65 64 2c 20 67 |nting th|e red, g|
|000038e0| 72 65 65 6e 2c 20 61 6e | 64 20 62 6c 75 65 20 63 |reen, an|d blue c|
|000038f0| 6f 6d 70 6f 6e 65 6e 74 | 73 20 6f 66 20 61 6e 20 |omponent|s of an |
|00003900| 69 6d 61 67 65 2e 20 41 | 74 20 65 61 63 68 20 6c |image. A|t each l|
|00003910| 65 76 65 6c 20 6f 66 20 | 74 68 65 20 74 72 65 65 |evel of |the tree|
|00003920| 2c 20 74 68 65 20 63 6f | 6c 6f 72 73 20 61 72 65 |, the co|lors are|
|00003930| 20 70 6c 61 63 65 64 20 | 69 6e 20 74 68 65 20 62 | placed |in the b|
|00003940| 72 61 6e 63 68 20 6f 66 | 20 74 68 65 20 74 72 65 |ranch of| the tre|
|00003950| 65 20 69 6e 64 69 63 61 | 74 65 64 20 62 79 20 74 |e indica|ted by t|
|00003960| 68 65 20 63 6f 72 72 65 | 73 70 6f 6e 64 69 6e 67 |he corre|sponding|
|00003970| 20 62 69 74 73 20 6f 66 | 20 74 68 65 20 72 65 64 | bits of| the red|
|00003980| 2c 20 67 72 65 65 6e 2c | 20 61 6e 64 20 62 6c 75 |, green,| and blu|
|00003990| 65 20 63 6f 6d 70 6f 6e | 65 6e 74 73 2e 20 46 6f |e compon|ents. Fo|
|000039a0| 72 20 69 6e 73 74 61 6e | 63 65 2c 20 73 61 79 20 |r instan|ce, say |
|000039b0| 61 20 63 6f 6c 6f 72 20 | 63 6f 6e 73 69 73 74 73 |a color |consists|
|000039c0| 20 6f 66 20 6f 6e 65 20 | 62 69 74 20 6f 66 20 72 | of one |bit of r|
|000039d0| 65 64 2c 20 6f 6e 65 20 | 62 69 74 20 6f 66 20 62 |ed, one |bit of b|
|000039e0| 6c 75 65 2c 20 61 6e 64 | 20 6f 6e 65 20 62 69 74 |lue, and| one bit|
|000039f0| 20 6f 66 20 67 72 65 65 | 6e 2e 20 54 68 65 20 30 | of gree|n. The 0|
|00003a00| 2d 30 2d 30 20 28 72 65 | 64 2d 67 72 65 65 6e 2d |-0-0 (re|d-green-|
|00003a10| 62 6c 75 65 29 20 63 6f | 6c 6f 72 20 77 69 6c 6c |blue) co|lor will|
|00003a20| 20 62 65 20 74 68 65 20 | 66 69 72 73 74 20 65 6e | be the |first en|
|00003a30| 74 72 79 20 69 6e 20 74 | 68 65 20 6e 6f 64 65 2c |try in t|he node,|
|00003a40| 20 74 68 65 20 30 2d 30 | 2d 31 20 63 6f 6c 6f 72 | the 0-0|-1 color|
|00003a50| 20 77 69 6c 6c 20 62 65 | 20 74 68 65 20 73 65 63 | will be| the sec|
|00003a60| 6f 6e 64 20 65 6e 74 72 | 79 20 69 6e 20 74 68 65 |ond entr|y in the|
|00003a70| 20 6e 6f 64 65 2c 20 61 | 6e 64 20 74 68 65 20 31 | node, a|nd the 1|
|00003a80| 2d 31 2d 31 20 63 6f 6c | 6f 72 20 77 69 6c 6c 20 |-1-1 col|or will |
|00003a90| 62 65 20 74 68 65 20 65 | 69 67 68 74 68 20 65 6e |be the e|ighth en|
|00003aa0| 74 72 79 20 69 6e 20 74 | 68 65 20 6e 6f 64 65 2e |try in t|he node.|
|00003ab0| 20 41 73 74 75 74 65 20 | 72 65 61 64 65 72 73 20 | Astute |readers |
|00003ac0| 77 69 6c 6c 20 6e 6f 74 | 69 63 65 20 74 68 61 74 |will not|ice that|
|00003ad0| 20 74 6f 20 64 65 74 65 | 72 6d 69 6e 65 20 77 68 | to dete|rmine wh|
|00003ae0| 69 63 68 20 65 6e 74 72 | 79 20 61 20 63 6f 6c 6f |ich entr|y a colo|
|00003af0| 72 20 73 68 6f 75 6c 64 | 20 62 65 2c 20 77 65 20 |r should| be, we |
|00003b00| 73 69 6d 70 6c 79 20 75 | 73 65 20 74 68 65 20 63 |simply u|se the c|
|00003b10| 6f 6c 6f 72 20 76 61 6c | 75 65 20 69 74 73 65 6c |olor val|ue itsel|
|00003b20| 66 20 61 73 20 61 20 7a | 65 72 6f 2d 62 61 73 65 |f as a z|ero-base|
|00003b30| 64 20 69 6e 64 65 78 20 | 69 6e 74 6f 20 74 68 65 |d index |into the|
|00003b40| 20 6e 6f 64 65 2e 0d 4f | 75 72 20 6f 63 74 72 65 | node..O|ur octre|
|00003b50| 65 20 6d 75 73 74 20 64 | 65 61 6c 20 77 69 74 68 |e must d|eal with|
|00003b60| 20 65 69 67 68 74 20 62 | 69 74 73 20 6f 66 20 72 | eight b|its of r|
|00003b70| 65 64 2c 20 67 72 65 65 | 6e 2c 20 61 6e 64 20 62 |ed, gree|n, and b|
|00003b80| 6c 75 65 20 66 6f 72 20 | 65 61 63 68 20 63 6f 6c |lue for |each col|
|00003b90| 6f 72 2c 20 62 75 74 20 | 74 68 69 73 20 69 73 20 |or, but |this is |
|00003ba0| 61 6e 20 65 61 73 79 20 | 65 78 74 65 6e 73 69 6f |an easy |extensio|
|00003bb0| 6e 20 6f 66 20 74 68 65 | 20 70 72 65 76 69 6f 75 |n of the| previou|
|00003bc0| 73 20 63 61 73 65 2e 20 | 54 6f 20 68 61 6e 64 6c |s case. |To handl|
|00003bd0| 65 20 6d 75 6c 74 69 70 | 6c 65 20 62 69 74 73 20 |e multip|le bits |
|00003be0| 6f 66 20 63 6f 6c 6f 72 | 20 69 6e 66 6f 72 6d 61 |of color| informa|
|00003bf0| 74 69 6f 6e 2c 20 74 68 | 65 20 63 6f 64 65 20 65 |tion, th|e code e|
|00003c00| 78 74 72 61 63 74 73 20 | 74 68 65 20 68 69 67 68 |xtracts |the high|
|00003c10| 65 73 74 20 62 69 74 20 | 6f 66 20 65 61 63 68 20 |est bit |of each |
|00003c20| 6f 66 20 74 68 65 20 72 | 65 64 2c 20 67 72 65 65 |of the r|ed, gree|
|00003c30| 6e 2c 20 61 6e 64 20 62 | 6c 75 65 20 63 6f 6d 70 |n, and b|lue comp|
|00003c40| 6f 6e 65 6e 74 73 20 6f | 66 20 74 68 65 20 63 6f |onents o|f the co|
|00003c50| 6c 6f 72 20 61 6e 64 20 | 75 73 65 73 20 74 68 69 |lor and |uses thi|
|00003c60| 73 20 61 73 20 61 6e 20 | 69 6e 64 65 78 20 69 6e |s as an |index in|
|00003c70| 74 6f 20 74 68 65 20 6c | 65 76 65 6c 2d 30 20 6e |to the l|evel-0 n|
|00003c80| 6f 64 65 20 74 6f 20 66 | 69 6e 64 20 74 68 65 20 |ode to f|ind the |
|00003c90| 6c 65 76 65 6c 2d 31 20 | 6e 6f 64 65 2e 20 54 68 |level-1 |node. Th|
|00003ca0| 65 6e 20 74 68 65 20 6e | 65 78 74 20 68 69 67 68 |en the n|ext high|
|00003cb0| 65 73 74 20 62 69 74 20 | 6f 66 20 65 61 63 68 20 |est bit |of each |
|00003cc0| 63 6f 6d 70 6f 6e 65 6e | 74 20 69 73 20 65 78 74 |componen|t is ext|
|00003cd0| 72 61 63 74 65 64 20 61 | 6e 64 20 75 73 65 64 20 |racted a|nd used |
|00003ce0| 61 73 20 61 6e 20 69 6e | 64 65 78 20 69 6e 74 6f |as an in|dex into|
|00003cf0| 20 74 68 69 73 20 6c 65 | 76 65 6c 2d 31 20 6e 6f | this le|vel-1 no|
|00003d00| 64 65 20 74 6f 20 66 69 | 6e 64 20 74 68 65 20 6c |de to fi|nd the l|
|00003d10| 65 76 65 6c 2d 32 20 6e | 6f 64 65 2e 20 54 68 69 |evel-2 n|ode. Thi|
|00003d20| 73 20 70 72 6f 63 65 73 | 73 20 63 6f 6e 74 69 6e |s proces|s contin|
|00003d30| 75 65 73 20 64 6f 77 6e | 20 74 6f 20 74 68 65 20 |ues down| to the |
|00003d40| 6c 6f 77 65 73 74 20 62 | 69 74 2c 20 77 68 69 63 |lowest b|it, whic|
|00003d50| 68 20 69 73 20 75 73 65 | 64 20 61 73 20 61 6e 20 |h is use|d as an |
|00003d60| 69 6e 64 65 78 20 69 6e | 74 6f 20 74 68 65 20 6c |index in|to the l|
|00003d70| 65 76 65 6c 2d 37 20 6e | 6f 64 65 20 74 6f 20 66 |evel-7 n|ode to f|
|00003d80| 69 6e 64 20 74 68 65 20 | 63 6f 6c 6f 72 20 72 65 |ind the |color re|
|00003d90| 63 6f 72 64 20 28 61 20 | 6c 65 76 65 6c 2d 38 20 |cord (a |level-8 |
|00003da0| 6c 65 61 66 29 2e 0d 54 | 68 65 20 61 63 74 75 61 |leaf)..T|he actua|
|00003db0| 6c 20 63 6f 6c 6f 72 20 | 73 65 6c 65 63 74 69 6f |l color |selectio|
|00003dc0| 6e 20 64 65 74 61 69 6c | 73 20 6f 66 20 74 68 65 |n detail|s of the|
|00003dd0| 20 6f 63 74 72 65 65 20 | 6d 65 74 68 6f 64 20 61 | octree |method a|
|00003de0| 72 65 20 6d 75 63 68 20 | 65 61 73 69 65 72 20 74 |re much |easier t|
|00003df0| 6f 20 75 6e 64 65 72 73 | 74 61 6e 64 20 69 6e 20 |o unders|tand in |
|00003e00| 74 77 6f 20 64 69 6d 65 | 6e 73 69 6f 6e 73 2c 20 |two dime|nsions, |
|00003e10| 6a 75 73 74 20 61 73 20 | 74 68 65 20 63 6f 72 65 |just as |the core|
|00003e20| 20 6f 66 20 74 68 65 20 | 6d 65 64 69 61 6e 20 6d | of the |median m|
|00003e30| 65 74 68 6f 64 20 77 61 | 73 2e 20 49 6e 20 74 77 |ethod wa|s. In tw|
|00003e40| 6f 20 64 69 6d 65 6e 73 | 69 6f 6e 73 20 77 65 d5 |o dimens|ions we.|
|00003e50| 72 65 20 77 6f 72 6b 69 | 6e 67 20 77 69 74 68 20 |re worki|ng with |
|00003e60| 61 20 71 75 61 64 74 72 | 65 65 20 69 6e 73 74 65 |a quadtr|ee inste|
|00003e70| 61 64 20 6f 66 20 61 6e | 20 6f 63 74 72 65 65 2e |ad of an| octree.|
|00003e80| 20 41 20 71 75 61 64 74 | 72 65 65 20 68 61 73 20 | A quadt|ree has |
|00003e90| 66 6f 75 72 20 62 72 61 | 6e 63 68 65 73 20 61 74 |four bra|nches at|
|00003ea0| 20 65 61 63 68 20 6e 6f | 64 65 2c 20 61 73 20 69 | each no|de, as i|
|00003eb0| 6c 6c 75 73 74 72 61 74 | 65 64 20 69 6e 20 46 69 |llustrat|ed in Fi|
|00003ec0| 67 75 72 65 20 34 2e 20 | 28 4e 6f 74 65 20 74 68 |gure 4. |(Note th|
|00003ed0| 61 74 20 62 65 6c 6f 77 | 20 6c 65 76 65 6c 20 31 |at below| level 1|
|00003ee0| 20 6f 6e 6c 79 20 6f 6e | 65 20 62 72 61 6e 63 68 | only on|e branch|
|00003ef0| 20 70 65 72 20 6e 6f 64 | 65 20 69 73 20 66 6f 6c | per nod|e is fol|
|00003f00| 6c 6f 77 65 64 20 74 6f | 20 61 20 64 65 65 70 65 |lowed to| a deepe|
|00003f10| 72 20 6c 65 76 65 6c 2c | 20 66 6f 72 20 74 68 65 |r level,| for the|
|00003f20| 20 73 61 6b 65 20 6f 66 | 20 73 69 6d 70 6c 69 66 | sake of| simplif|
|00003f30| 79 69 6e 67 20 74 68 65 | 20 64 72 61 77 69 6e 67 |ying the| drawing|
|00003f40| 2e 20 49 6e 20 72 65 61 | 6c 69 74 79 2c 20 65 61 |. In rea|lity, ea|
|00003f50| 63 68 20 6e 6f 64 65 20 | 73 70 72 6f 75 74 73 20 |ch node |sprouts |
|00003f60| 66 6f 75 72 20 62 72 61 | 6e 63 68 65 73 2c 20 65 |four bra|nches, e|
|00003f70| 61 63 68 20 6f 66 20 77 | 68 69 63 68 20 69 6e 20 |ach of w|hich in |
|00003f80| 74 75 72 6e 20 73 70 72 | 6f 75 74 73 20 66 6f 75 |turn spr|outs fou|
|00003f90| 72 20 6d 6f 72 65 2c 20 | 61 6e 64 20 73 6f 20 6f |r more, |and so o|
|00003fa0| 6e 20 74 6f 20 74 68 65 | 20 64 65 65 70 65 73 74 |n to the| deepest|
|00003fb0| 20 6c 65 76 65 6c 2e 29 | 20 43 6f 6c 6f 72 73 20 | level.)| Colors |
|00003fc0| 61 72 65 20 69 6e 73 65 | 72 74 65 64 20 69 6e 74 |are inse|rted int|
|00003fd0| 6f 20 74 68 65 20 71 75 | 61 64 74 72 65 65 20 6d |o the qu|adtree m|
|00003fe0| 75 63 68 20 61 73 20 74 | 68 65 79 20 77 6f 75 6c |uch as t|hey woul|
|00003ff0| 64 20 62 65 20 69 6e 20 | 61 6e 20 6f 63 74 72 65 |d be in |an octre|
|00004000| 65 2c 20 65 78 63 65 70 | 74 20 74 68 61 74 20 74 |e, excep|t that t|
|00004010| 68 65 20 62 6c 75 65 20 | 63 6f 6d 70 6f 6e 65 6e |he blue |componen|
|00004020| 74 20 69 73 20 6d 69 73 | 73 69 6e 67 2e 20 46 6f |t is mis|sing. Fo|
|00004030| 72 20 69 6e 73 74 61 6e | 63 65 2c 20 74 68 65 20 |r instan|ce, the |
|00004040| 30 2d 30 20 28 72 65 64 | 2d 67 72 65 65 6e 29 20 |0-0 (red|-green) |
|00004050| 63 6f 6c 6f 72 20 69 73 | 20 74 68 65 20 66 69 72 |color is| the fir|
|00004060| 73 74 20 65 6e 74 72 79 | 20 69 6e 20 74 68 65 20 |st entry| in the |
|00004070| 6e 6f 64 65 2c 20 74 68 | 65 20 30 2d 31 20 63 6f |node, th|e 0-1 co|
|00004080| 6c 6f 72 20 69 73 20 74 | 68 65 20 73 65 63 6f 6e |lor is t|he secon|
|00004090| 64 20 65 6e 74 72 79 2c | 20 61 6e 64 20 74 68 65 |d entry,| and the|
|000040a0| 20 31 2d 31 20 63 6f 6c | 6f 72 20 69 73 20 74 68 | 1-1 col|or is th|
|000040b0| 65 20 66 6f 75 72 74 68 | 20 65 6e 74 72 79 2e 20 |e fourth| entry. |
|000040c0| 54 68 75 73 2c 20 74 68 | 65 20 74 77 6f 2d 64 69 |Thus, th|e two-di|
|000040d0| 6d 65 6e 73 69 6f 6e 61 | 6c 20 63 6f 6c 6f 72 20 |mensiona|l color |
|000040e0| 76 61 6c 75 65 20 63 61 | 6e 20 73 74 69 6c 6c 20 |value ca|n still |
|000040f0| 62 65 20 75 73 65 64 20 | 61 73 20 61 20 7a 65 72 |be used |as a zer|
|00004100| 6f 2d 62 61 73 65 64 20 | 69 6e 64 65 78 20 69 6e |o-based |index in|
|00004110| 74 6f 20 74 68 65 20 6e | 6f 64 65 2e 0d 57 65 20 |to the n|ode..We |
|00004120| 74 68 69 6e 6b 20 6f 66 | 20 74 68 69 73 20 71 75 |think of| this qu|
|00004130| 61 64 74 72 65 65 20 61 | 73 20 63 6f 72 72 65 73 |adtree a|s corres|
|00004140| 70 6f 6e 64 69 6e 67 20 | 74 6f 20 61 20 63 6f 6f |ponding |to a coo|
|00004150| 72 64 69 6e 61 74 65 20 | 70 6c 61 6e 65 20 66 6f |rdinate |plane fo|
|00004160| 72 6d 65 64 20 62 79 20 | 74 77 6f 20 63 6f 6c 6f |rmed by |two colo|
|00004170| 72 20 61 78 65 73 3b 20 | 65 61 63 68 20 62 72 61 |r axes; |each bra|
|00004180| 6e 63 68 20 74 68 65 6e | 20 63 6f 72 72 65 73 70 |nch then| corresp|
|00004190| 6f 6e 64 73 20 74 6f 20 | 61 20 71 75 61 64 72 61 |onds to |a quadra|
|000041a0| 6e 74 20 6f 66 20 74 68 | 65 20 73 70 61 63 65 20 |nt of th|e space |
|000041b0| 63 6f 76 65 72 65 64 20 | 62 79 20 74 68 65 20 70 |covered |by the p|
|000041c0| 61 72 65 6e 74 20 6e 6f | 64 65 2e 20 46 6f 72 20 |arent no|de. For |
|000041d0| 69 6e 73 74 61 6e 63 65 | 2c 20 69 66 20 61 20 71 |instance|, if a q|
|000041e0| 75 61 64 74 72 65 65 20 | 69 73 20 62 65 69 6e 67 |uadtree |is being|
|000041f0| 20 75 73 65 64 20 74 6f | 20 72 65 70 72 65 73 65 | used to| represe|
|00004200| 6e 74 20 74 68 65 20 72 | 65 64 2d 67 72 65 65 6e |nt the r|ed-green|
|00004210| 20 70 6c 61 6e 65 20 6f | 66 20 61 6e 20 52 47 42 | plane o|f an RGB|
|00004220| 20 63 75 62 65 20 77 69 | 74 68 20 65 61 63 68 20 | cube wi|th each |
|00004230| 61 78 69 73 20 72 61 6e | 67 69 6e 67 20 66 72 6f |axis ran|ging fro|
|00004240| 6d 20 30 20 74 6f 20 38 | 2c 20 74 68 65 20 66 6f |m 0 to 8|, the fo|
|00004250| 75 72 20 6c 65 76 65 6c | 2d 31 20 6e 6f 64 65 73 |ur level|-1 nodes|
|00004260| 20 72 65 70 72 65 73 65 | 6e 74 20 74 68 65 20 66 | represe|nt the f|
|00004270| 6f 75 72 20 71 75 61 64 | 72 61 6e 74 73 20 6f 66 |our quad|rants of|
|00004280| 20 74 68 69 73 20 70 6c | 61 6e 65 20 64 65 66 69 | this pl|ane defi|
|00004290| 6e 65 64 20 62 79 20 28 | 72 65 64 20 30 2d 34 2c |ned by (|red 0-4,|
|000042a0| 20 67 72 65 65 6e 20 30 | 2d 34 29 2c 20 28 72 65 | green 0|-4), (re|
|000042b0| 64 20 34 2d 38 2c 20 67 | 72 65 65 6e 20 30 2d 34 |d 4-8, g|reen 0-4|
|000042c0| 29 2c 20 28 72 65 64 20 | 30 2d 34 2c 20 67 72 65 |), (red |0-4, gre|
|000042d0| 65 6e 20 34 2d 38 29 2c | 20 61 6e 64 20 28 72 65 |en 4-8),| and (re|
|000042e0| 64 20 34 2d 38 2c 20 67 | 72 65 65 6e 20 34 2d 38 |d 4-8, g|reen 4-8|
|000042f0| 29 2e 20 54 68 65 20 6c | 65 76 65 6c 2d 32 20 6e |). The l|evel-2 n|
|00004300| 6f 64 65 73 20 6f 66 20 | 74 68 65 20 28 72 65 64 |odes of |the (red|
|00004310| 20 30 2d 34 2c 20 67 72 | 65 65 6e 20 30 2d 34 29 | 0-4, gr|een 0-4)|
|00004320| 20 71 75 61 64 72 61 6e | 74 20 72 65 70 72 65 73 | quadran|t repres|
|00004330| 65 6e 74 20 74 68 65 20 | 66 6f 75 72 20 71 75 61 |ent the |four qua|
|00004340| 72 74 65 72 73 20 6f 66 | 20 74 68 69 73 20 70 61 |rters of| this pa|
|00004350| 72 74 69 63 75 6c 61 72 | 20 71 75 61 64 72 61 6e |rticular| quadran|
|00004360| 74 2c 20 61 6e 64 20 73 | 6f 20 6f 6e 20 64 6f 77 |t, and s|o on dow|
|00004370| 6e 20 74 6f 20 74 68 65 | 20 64 65 65 70 65 73 74 |n to the| deepest|
|00004380| 20 6c 65 76 65 6c 2e 20 | 4f 66 20 63 6f 75 72 73 | level. |Of cours|
|00004390| 65 2c 20 69 6e 20 74 68 | 65 20 63 61 73 65 20 6f |e, in th|e case o|
|000043a0| 66 20 74 68 65 20 6f 63 | 74 72 65 65 20 28 74 68 |f the oc|tree (th|
|000043b0| 65 20 73 74 72 75 63 74 | 75 72 65 20 74 68 61 74 |e struct|ure that|
|000043c0| 20 6f 75 72 20 0d 0d 46 | 69 67 75 72 65 20 34 0d | our ..F|igure 4.|
|000043d0| 41 20 46 69 76 65 2d 4c | 65 76 65 6c 20 51 75 61 |A Five-L|evel Qua|
|000043e0| 64 74 72 65 65 0d 61 6c | 67 6f 72 69 74 68 6d 20 |dtree.al|gorithm |
|000043f0| 61 63 74 75 61 6c 6c 79 | 20 75 73 65 73 29 2c 20 |actually| uses), |
|00004400| 74 68 65 20 65 69 67 68 | 74 20 62 72 61 6e 63 68 |the eigh|t branch|
|00004410| 65 73 20 63 6f 6e 74 61 | 69 6e 65 64 20 62 79 20 |es conta|ined by |
|00004420| 61 20 6e 6f 64 65 20 63 | 6f 72 72 65 73 70 6f 6e |a node c|orrespon|
|00004430| 64 20 74 6f 20 74 68 65 | 20 65 69 67 68 74 20 73 |d to the| eight s|
|00004440| 75 62 63 75 62 65 73 20 | 6f 66 20 74 68 65 20 73 |ubcubes |of the s|
|00004450| 70 61 63 65 20 72 65 70 | 72 65 73 65 6e 74 65 64 |pace rep|resented|
|00004460| 20 62 79 20 74 68 65 20 | 65 6e 74 69 72 65 20 6e | by the |entire n|
|00004470| 6f 64 65 2e 0d 54 68 65 | 20 6f 63 74 72 65 65 20 |ode..The| octree |
|00004480| 61 6c 67 6f 72 69 74 68 | 6d 20 66 69 72 73 74 20 |algorith|m first |
|00004490| 61 64 64 73 20 63 6f 6c | 6f 72 73 20 28 6c 65 61 |adds col|ors (lea|
|000044a0| 76 65 73 29 20 74 6f 20 | 74 68 65 20 74 72 65 65 |ves) to |the tree|
|000044b0| 20 75 6e 74 69 6c 20 74 | 68 65 72 65 20 69 73 20 | until t|here is |
|000044c0| 6f 6e 65 20 6d 6f 72 65 | 20 63 6f 6c 6f 72 20 28 |one more| color (|
|000044d0| 6c 65 61 66 29 20 74 68 | 61 6e 20 72 65 71 75 65 |leaf) th|an reque|
|000044e0| 73 74 65 64 2e 20 54 68 | 65 6e 20 74 68 65 20 74 |sted. Th|en the t|
|000044f0| 72 65 65 20 69 73 20 72 | 65 64 75 63 65 64 20 73 |ree is r|educed s|
|00004500| 6f 20 74 68 61 74 20 74 | 68 65 72 65 20 61 72 65 |o that t|here are|
|00004510| 20 6e 6f 20 6d 6f 72 65 | 20 6c 65 61 76 65 73 20 | no more| leaves |
|00004520| 74 68 61 6e 20 63 6f 6c | 6f 72 73 20 72 65 71 75 |than col|ors requ|
|00004530| 65 73 74 65 64 2e 20 54 | 68 65 20 72 65 64 75 63 |ested. T|he reduc|
|00004540| 74 69 6f 6e 20 70 72 6f | 63 65 73 73 20 73 74 61 |tion pro|cess sta|
|00004550| 72 74 73 20 6f 6e 20 74 | 68 65 20 64 65 65 70 65 |rts on t|he deepe|
|00004560| 73 74 20 6c 65 76 65 6c | 20 61 6e 64 20 61 74 74 |st level| and att|
|00004570| 65 6d 70 74 73 20 74 6f | 20 66 69 6e 64 20 74 77 |empts to| find tw|
|00004580| 6f 20 6f 72 20 6d 6f 72 | 65 20 6c 65 61 76 65 73 |o or mor|e leaves|
|00004590| 20 74 68 61 74 20 68 61 | 76 65 20 74 68 65 20 73 | that ha|ve the s|
|000045a0| 61 6d 65 20 70 61 72 65 | 6e 74 2e 20 49 66 20 74 |ame pare|nt. If t|
|000045b0| 68 69 73 20 63 6f 6e 64 | 69 74 69 6f 6e 20 69 73 |his cond|ition is|
|000045c0| 20 6e 6f 74 20 6d 65 74 | 20 6f 6e 20 74 68 65 20 | not met| on the |
|000045d0| 64 65 65 70 65 73 74 20 | 6c 65 76 65 6c 2c 20 74 |deepest |level, t|
|000045e0| 68 65 20 73 65 61 72 63 | 68 20 63 6f 6e 74 69 6e |he searc|h contin|
|000045f0| 75 65 73 20 75 70 20 74 | 6f 20 74 68 65 20 6e 65 |ues up t|o the ne|
|00004600| 78 74 20 6c 65 76 65 6c | 20 75 6e 74 69 6c 20 6d |xt level| until m|
|00004610| 75 6c 74 69 70 6c 65 20 | 6c 65 61 76 65 73 20 77 |ultiple |leaves w|
|00004620| 69 74 68 20 74 68 65 20 | 73 61 6d 65 20 70 61 72 |ith the |same par|
|00004630| 65 6e 74 20 61 72 65 20 | 66 6f 75 6e 64 2e 20 54 |ent are |found. T|
|00004640| 68 65 73 65 20 6c 65 61 | 76 65 73 20 61 72 65 20 |hese lea|ves are |
|00004650| 74 68 65 6e 20 72 65 64 | 75 63 65 64 20 74 6f 20 |then red|uced to |
|00004660| 74 68 65 20 70 61 72 65 | 6e 74 20 6e 6f 64 65 2e |the pare|nt node.|
|00004670| 20 54 68 65 20 70 72 6f | 63 65 73 73 20 63 6f 6e | The pro|cess con|
|00004680| 74 69 6e 75 65 73 20 75 | 6e 74 69 6c 20 74 68 65 |tinues u|ntil the|
|00004690| 20 74 72 65 65 20 63 6f | 6e 74 61 69 6e 73 20 6e | tree co|ntains n|
|000046a0| 6f 20 6d 6f 72 65 20 74 | 68 61 6e 20 74 68 65 20 |o more t|han the |
|000046b0| 6e 75 6d 62 65 72 20 6f | 66 20 63 6f 6c 6f 72 73 |number o|f colors|
|000046c0| 20 28 6c 65 61 76 65 73 | 29 20 72 65 71 75 65 73 | (leaves|) reques|
|000046d0| 74 65 64 20 61 6e 64 20 | 6e 6f 20 6d 6f 72 65 20 |ted and |no more |
|000046e0| 63 6f 6c 6f 72 73 20 72 | 65 6d 61 69 6e 20 74 6f |colors r|emain to|
|000046f0| 20 62 65 20 61 64 64 65 | 64 2e 20 54 68 65 20 66 | be adde|d. The f|
|00004700| 69 6e 61 6c 20 63 6f 6c | 6f 72 20 66 6f 72 20 65 |inal col|or for e|
|00004710| 61 63 68 20 6c 65 61 66 | 20 69 6e 20 74 68 65 20 |ach leaf| in the |
|00004720| 74 72 65 65 20 69 73 20 | 64 65 74 65 72 6d 69 6e |tree is |determin|
|00004730| 65 64 20 62 79 20 63 61 | 6c 63 75 6c 61 74 69 6e |ed by ca|lculatin|
|00004740| 67 20 61 20 77 65 69 67 | 68 74 65 64 20 61 76 65 |g a weig|hted ave|
|00004750| 72 61 67 65 20 6f 66 20 | 61 6c 6c 20 74 68 65 20 |rage of |all the |
|00004760| 63 6f 6c 6f 72 73 20 72 | 65 64 75 63 65 64 20 74 |colors r|educed t|
|00004770| 6f 20 74 68 61 74 20 6c | 65 61 66 2e 0d 4f 6e 65 |o that l|eaf..One|
|00004780| 20 6d 61 6a 6f 72 20 64 | 69 66 66 65 72 65 6e 63 | major d|ifferenc|
|00004790| 65 20 74 68 61 74 20 64 | 69 73 74 69 6e 67 75 69 |e that d|istingui|
|000047a0| 73 68 65 73 20 6f 75 72 | 20 6f 63 74 72 65 65 20 |shes our| octree |
|000047b0| 69 6d 70 6c 65 6d 65 6e | 74 61 74 69 6f 6e 20 66 |implemen|tation f|
|000047c0| 72 6f 6d 20 74 68 65 20 | 6d 65 64 69 61 6e 20 6f |rom the |median o|
|000047d0| 72 20 70 6f 70 75 6c 61 | 72 20 6d 65 74 68 6f 64 |r popula|r method|
|000047e0| 20 69 73 20 74 68 65 20 | 77 61 79 20 74 68 61 74 | is the |way that|
|000047f0| 20 63 6f 6c 6f 72 73 20 | 61 72 65 20 72 65 63 6f | colors |are reco|
|00004800| 72 64 65 64 2e 20 54 68 | 65 20 6f 63 74 72 65 65 |rded. Th|e octree|
|00004810| 20 6d 65 74 68 6f 64 20 | 63 61 6c 63 75 6c 61 74 | method |calculat|
|00004820| 65 73 20 74 68 65 20 73 | 65 74 20 6f 66 20 62 65 |es the s|et of be|
|00004830| 73 74 20 63 6f 6c 6f 72 | 73 20 28 72 65 64 75 63 |st color|s (reduc|
|00004840| 65 73 20 6e 6f 64 65 73 | 29 20 61 73 20 74 68 65 |es nodes|) as the|
|00004850| 20 73 6f 75 72 63 65 20 | 63 6f 6c 6f 72 73 20 61 | source |colors a|
|00004860| 72 65 20 62 65 69 6e 67 | 20 61 64 64 65 64 20 74 |re being| added t|
|00004870| 6f 20 74 68 65 20 74 72 | 65 65 2c 20 69 6e 73 74 |o the tr|ee, inst|
|00004880| 65 61 64 20 6f 66 20 63 | 6f 75 6e 74 69 6e 67 20 |ead of c|ounting |
|00004890| 61 6e 64 20 73 74 6f 72 | 69 6e 67 20 61 6c 6c 20 |and stor|ing all |
|000048a0| 74 68 65 20 63 6f 6c 6f | 72 73 20 62 65 66 6f 72 |the colo|rs befor|
|000048b0| 65 20 62 65 67 69 6e 6e | 69 6e 67 20 74 6f 20 70 |e beginn|ing to p|
|000048c0| 61 72 65 20 74 68 65 6d | 20 64 6f 77 6e 2e 20 54 |are them| down. T|
|000048d0| 68 69 73 20 69 73 20 6e | 6f 74 20 61 6e 20 69 6e |his is n|ot an in|
|000048e0| 68 65 72 65 6e 74 20 6c | 69 6d 69 74 61 74 69 6f |herent l|imitatio|
|000048f0| 6e 20 6f 66 20 6f 63 74 | 72 65 65 73 20 69 6e 20 |n of oct|rees in |
|00004900| 67 65 6e 65 72 61 6c 3b | 20 77 65 20 73 69 6d 70 |general;| we simp|
|00004910| 6c 79 20 63 68 6f 73 65 | 20 74 68 69 73 20 69 6d |ly chose| this im|
|00004920| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 20 74 6f 20 |plementa|tion to |
|00004930| 72 65 64 75 63 65 20 6f | 75 72 20 6d 65 6d 6f 72 |reduce o|ur memor|
|00004940| 79 20 72 65 71 75 69 72 | 65 6d 65 6e 74 73 20 61 |y requir|ements a|
|00004950| 6e 64 20 74 6f 20 6d 61 | 6b 65 20 74 68 65 73 65 |nd to ma|ke these|
|00004960| 20 72 65 71 75 69 72 65 | 6d 65 6e 74 73 20 69 6e | require|ments in|
|00004970| 64 65 70 65 6e 64 65 6e | 74 20 6f 66 20 74 68 65 |dependen|t of the|
|00004980| 20 63 6f 6d 70 6c 65 78 | 69 74 79 20 6f 66 20 74 | complex|ity of t|
|00004990| 68 65 20 69 6d 61 67 65 | 2e 20 54 68 65 20 64 69 |he image|. The di|
|000049a0| 73 61 64 76 61 6e 74 61 | 67 65 20 6f 66 20 74 68 |sadvanta|ge of th|
|000049b0| 69 73 20 63 68 6f 69 63 | 65 20 69 73 20 74 68 61 |is choic|e is tha|
|000049c0| 74 20 74 68 65 20 6f 63 | 74 72 65 65 20 6d 65 74 |t the oc|tree met|
|000049d0| 68 6f 64 20 6d 75 73 74 | 20 6d 61 6b 65 20 64 65 |hod must| make de|
|000049e0| 63 69 73 69 6f 6e 73 20 | 6f 6e 20 77 68 69 63 68 |cisions |on which|
|000049f0| 20 63 6f 6c 6f 72 73 20 | 74 6f 20 74 68 72 6f 77 | colors |to throw|
|00004a00| 20 6f 75 74 20 62 61 73 | 65 64 20 6f 6e 20 69 6e | out bas|ed on in|
|00004a10| 63 6f 6d 70 6c 65 74 65 | 20 69 6e 66 6f 72 6d 61 |complete| informa|
|00004a20| 74 69 6f 6e 2e 41 6e 6f | 74 68 65 72 20 69 6e 74 |tion.Ano|ther int|
|00004a30| 65 72 65 73 74 69 6e 67 | 20 64 69 66 66 65 72 65 |eresting| differe|
|00004a40| 6e 63 65 20 69 73 20 74 | 68 61 74 20 74 68 65 20 |nce is t|hat the |
|00004a50| 6f 63 74 72 65 65 20 61 | 6c 67 6f 72 69 74 68 6d |octree a|lgorithm|
|00004a60| 20 63 61 6e 20 61 63 74 | 75 61 6c 6c 79 20 72 65 | can act|ually re|
|00004a70| 74 75 72 6e 20 66 65 77 | 65 72 20 63 6f 6c 6f 72 |turn few|er color|
|00004a80| 73 20 74 68 61 6e 20 72 | 65 71 75 65 73 74 65 64 |s than r|equested|
|00004a90| 2c 20 69 6e 73 74 65 61 | 64 20 6f 66 20 61 6c 77 |, instea|d of alw|
|00004aa0| 61 79 73 20 72 65 74 75 | 72 6e 69 6e 67 20 74 68 |ays retu|rning th|
|00004ab0| 65 20 65 78 61 63 74 20 | 6e 75 6d 62 65 72 2e 20 |e exact |number. |
|00004ac0| 54 68 65 6f 72 65 74 69 | 63 61 6c 6c 79 2c 20 74 |Theoreti|cally, t|
|00004ad0| 68 69 73 20 63 61 6e 20 | 72 65 64 75 63 65 20 74 |his can |reduce t|
|00004ae0| 68 65 20 61 63 63 75 72 | 61 63 79 20 6f 66 20 74 |he accur|acy of t|
|00004af0| 68 65 20 72 65 74 75 72 | 6e 65 64 20 63 6f 6c 6f |he retur|ned colo|
|00004b00| 72 20 73 65 74 2c 20 73 | 69 6e 63 65 20 74 68 65 |r set, s|ince the|
|00004b10| 72 65 20 61 72 65 20 66 | 65 77 65 72 20 63 6f 6c |re are f|ewer col|
|00004b20| 6f 72 73 20 74 6f 20 72 | 65 70 72 65 73 65 6e 74 |ors to r|epresent|
|00004b30| 20 74 68 65 20 66 75 6c | 6c 20 72 61 6e 67 65 20 | the ful|l range |
|00004b40| 61 6e 64 20 64 65 74 61 | 69 6c 20 6f 66 20 74 68 |and deta|il of th|
|00004b50| 65 20 70 69 63 74 75 72 | 65 2e 20 48 6f 77 65 76 |e pictur|e. Howev|
|00004b60| 65 72 2c 20 77 65 20 68 | 61 76 65 20 66 6f 75 6e |er, we h|ave foun|
|00004b70| 64 20 74 68 61 74 20 6d | 6f 73 74 20 69 6d 61 67 |d that m|ost imag|
|00004b80| 65 73 20 64 6f 20 72 65 | 74 75 72 6e 20 65 69 74 |es do re|turn eit|
|00004b90| 68 65 72 20 74 68 65 20 | 66 75 6c 6c 20 6e 75 6d |her the |full num|
|00004ba0| 62 65 72 20 6f 66 20 63 | 6f 6c 6f 72 73 20 72 65 |ber of c|olors re|
|00004bb0| 71 75 65 73 74 65 64 20 | 6f 72 20 6f 6e 6c 79 20 |quested |or only |
|00004bc0| 6f 6e 65 20 6f 72 20 74 | 77 6f 20 66 65 77 65 72 |one or t|wo fewer|
|00004bd0| 2e 0d 46 6f 72 20 70 75 | 72 70 6f 73 65 73 20 6f |..For pu|rposes o|
|00004be0| 66 20 63 6f 6d 70 61 72 | 69 73 6f 6e 2c 20 77 65 |f compar|ison, we|
|00004bf0| d5 6c 6c 20 64 69 73 63 | 75 73 73 20 68 6f 77 20 |.ll disc|uss how |
|00004c00| 74 68 65 20 6f 63 74 72 | 65 65 20 6d 65 74 68 6f |the octr|ee metho|
|00004c10| 64 20 70 69 63 6b 73 20 | 74 68 65 20 62 65 73 74 |d picks |the best|
|00004c20| 20 66 6f 75 72 20 63 6f | 6c 6f 72 73 20 69 6e 20 | four co|lors in |
|00004c30| 61 20 63 6f 6c 6f 72 20 | 70 6c 61 6e 65 20 77 68 |a color |plane wh|
|00004c40| 65 6e 20 67 69 76 65 6e | 20 74 68 65 20 73 61 6d |en given| the sam|
|00004c50| 65 20 65 69 67 68 74 20 | 63 6f 6c 6f 72 73 20 61 |e eight |colors a|
|00004c60| 73 20 75 73 65 64 20 69 | 6e 20 74 68 65 20 65 78 |s used i|n the ex|
|00004c70| 61 6d 70 6c 65 20 66 6f | 72 20 74 68 65 20 6d 65 |ample fo|r the me|
|00004c80| 64 69 61 6e 20 6d 65 74 | 68 6f 64 2e 20 54 68 65 |dian met|hod. The|
|00004c90| 20 70 72 6f 63 65 73 73 | 20 69 73 20 69 6c 6c 75 | process| is illu|
|00004ca0| 73 74 72 61 74 65 64 20 | 69 6e 20 46 69 67 75 72 |strated |in Figur|
|00004cb0| 65 20 35 2e 20 4e 6f 74 | 65 20 74 68 61 74 20 74 |e 5. Not|e that t|
|00004cc0| 68 65 20 71 75 61 64 74 | 72 65 65 20 69 73 20 72 |he quadt|ree is r|
|00004cd0| 65 70 72 65 73 65 6e 74 | 65 64 20 74 68 65 72 65 |epresent|ed there|
|00004ce0| 20 62 79 20 61 20 31 36 | 20 78 20 31 36 20 67 72 | by a 16| x 16 gr|
|00004cf0| 69 64 3b 20 65 61 63 68 | 20 70 6f 73 69 74 69 6f |id; each| positio|
|00004d00| 6e 20 69 6e 20 74 68 65 | 20 67 72 69 64 20 63 6f |n in the| grid co|
|00004d10| 72 72 65 73 70 6f 6e 64 | 73 20 74 6f 20 6f 6e 65 |rrespond|s to one|
|00004d20| 20 6f 66 20 74 68 65 20 | 6c 65 61 76 65 73 20 6f | of the |leaves o|
|00004d30| 6e 20 74 68 65 20 66 69 | 66 74 68 20 6c 65 76 65 |n the fi|fth leve|
|00004d40| 6c 20 6f 66 20 74 68 65 | 20 71 75 61 64 74 72 65 |l of the| quadtre|
|00004d50| 65 20 73 68 6f 77 6e 20 | 69 6e 20 46 69 67 75 72 |e shown |in Figur|
|00004d60| 65 20 34 2e 0d 46 69 67 | 75 72 65 20 35 0d 50 69 |e 4..Fig|ure 5.Pi|
|00004d70| 63 6b 69 6e 67 20 46 6f | 75 72 20 43 6f 6c 6f 72 |cking Fo|ur Color|
|00004d80| 73 20 55 73 69 6e 67 20 | 74 68 65 20 4f 63 74 72 |s Using |the Octr|
|00004d90| 65 65 20 4d 65 74 68 6f | 64 0d 49 6e 20 74 68 65 |ee Metho|d.In the|
|00004da0| 20 67 72 69 64 2c 20 65 | 61 63 68 20 63 6f 6c 6f | grid, e|ach colo|
|00004db0| 72 20 69 6e 69 74 69 61 | 6c 6c 79 20 6f 63 63 75 |r initia|lly occu|
|00004dc0| 70 69 65 73 20 69 74 73 | 20 6f 77 6e 20 74 69 6e |pies its| own tin|
|00004dd0| 79 20 62 6f 78 2e 20 54 | 68 65 20 63 6f 6c 6f 72 |y box. T|he color|
|00004de0| 20 73 65 6c 65 63 74 69 | 6f 6e 20 70 72 6f 63 65 | selecti|on proce|
|00004df0| 73 73 20 74 72 61 6e 73 | 6c 61 74 65 73 20 69 6e |ss trans|lates in|
|00004e00| 74 6f 20 63 6f 6c 6c 65 | 63 74 69 6e 67 20 74 68 |to colle|cting th|
|00004e10| 65 20 67 72 69 64 20 73 | 71 75 61 72 65 73 20 69 |e grid s|quares i|
|00004e20| 6e 74 6f 20 62 69 67 67 | 65 72 20 61 6e 64 20 62 |nto bigg|er and b|
|00004e30| 69 67 67 65 72 20 62 6f | 78 65 73 20 75 6e 74 69 |igger bo|xes unti|
|00004e40| 6c 20 6d 6f 72 65 20 74 | 68 61 6e 20 6f 6e 65 20 |l more t|han one |
|00004e50| 63 6f 6c 6f 72 20 66 61 | 6c 6c 73 20 69 6e 74 6f |color fa|lls into|
|00004e60| 20 61 20 73 69 6e 67 6c | 65 20 62 6f 78 2e 20 57 | a singl|e box. W|
|00004e70| 65 20 73 74 61 72 74 20 | 77 69 74 68 20 66 69 76 |e start |with fiv|
|00004e80| 65 20 63 6f 6c 6f 72 73 | 20 69 6e 20 73 74 65 70 |e colors| in step|
|00004e90| 20 31 2c 20 6f 6e 65 20 | 6d 6f 72 65 20 63 6f 6c | 1, one |more col|
|00004ea0| 6f 72 20 74 68 61 6e 20 | 72 65 71 75 65 73 74 65 |or than |requeste|
|00004eb0| 64 2e 20 54 68 65 20 72 | 65 64 75 63 74 69 6f 6e |d. The r|eduction|
|00004ec0| 20 66 72 6f 6d 20 73 74 | 65 70 20 31 20 74 6f 20 | from st|ep 1 to |
|00004ed0| 73 74 65 70 20 32 20 69 | 6e 20 74 68 65 20 66 69 |step 2 i|n the fi|
|00004ee0| 67 75 72 65 20 69 6e 76 | 6f 6c 76 65 73 72 65 64 |gure inv|olvesred|
|00004ef0| 75 63 69 6e 67 20 61 20 | 6e 6f 64 65 20 61 74 20 |ucing a |node at |
|00004f00| 74 68 65 20 66 6f 75 72 | 74 68 20 6c 65 76 65 6c |the four|th level|
|00004f10| 20 6f 66 20 74 68 65 20 | 71 75 61 64 74 72 65 65 | of the |quadtree|
|00004f20| 2c 20 63 72 65 61 74 69 | 6e 67 20 61 20 34 20 78 |, creati|ng a 4 x|
|00004f30| 20 34 20 62 6f 78 20 63 | 6f 6e 74 61 69 6e 69 6e | 4 box c|ontainin|
|00004f40| 67 20 74 77 6f 20 63 6f | 6c 6f 72 73 2e 20 48 61 |g two co|lors. Ha|
|00004f50| 64 20 61 20 66 69 66 74 | 68 2d 6c 65 76 65 6c 20 |d a fift|h-level |
|00004f60| 6e 6f 64 65 20 63 6f 6e | 74 61 69 6e 69 6e 67 20 |node con|taining |
|00004f70| 74 77 6f 20 63 6f 6c 6f | 72 73 20 62 65 65 6e 20 |two colo|rs been |
|00004f80| 66 6f 75 6e 64 2c 20 74 | 68 65 20 6e 65 77 20 62 |found, t|he new b|
|00004f90| 6f 78 20 77 6f 75 6c 64 | 20 62 65 20 32 20 78 20 |ox would| be 2 x |
|00004fa0| 32 20 72 61 74 68 65 72 | 20 74 68 61 6e 20 34 20 |2 rather| than 4 |
|00004fb0| 78 20 34 2e 0d 49 6e 20 | 73 74 65 70 20 33 2c 20 |x 4..In |step 3, |
|00004fc0| 61 6e 6f 74 68 65 72 20 | 63 6f 6c 6f 72 20 69 73 |another |color is|
|00004fd0| 20 61 64 64 65 64 20 61 | 6e 64 20 73 69 6e 63 65 | added a|nd since|
|00004fe0| 20 69 74 20 64 6f 65 73 | 6e d5 74 20 66 61 6c 6c | it does|n.t fall|
|00004ff0| 20 69 6e 74 6f 20 61 6e | 20 65 78 69 73 74 69 6e | into an| existin|
|00005000| 67 20 73 75 62 64 69 76 | 69 73 69 6f 6e 2c 20 74 |g subdiv|ision, t|
|00005010| 68 65 20 74 72 65 65 20 | 69 73 20 72 65 64 75 63 |he tree |is reduc|
|00005020| 65 64 20 61 67 61 69 6e | 2e 20 54 68 69 73 20 74 |ed again|. This t|
|00005030| 69 6d 65 20 61 6e 20 38 | 20 78 20 38 20 62 6f 78 |ime an 8| x 8 box|
|00005040| 2c 20 61 73 20 73 68 6f | 77 6e 20 69 6e 20 73 74 |, as sho|wn in st|
|00005050| 65 70 20 34 2c 20 69 73 | 20 66 6f 72 6d 65 64 2e |ep 4, is| formed.|
|00005060| 20 53 74 65 70 20 35 20 | 61 64 64 73 20 61 6e 6f | Step 5 |adds ano|
|00005070| 74 68 65 72 20 63 6f 6c | 6f 72 2c 20 62 75 74 20 |ther col|or, but |
|00005080| 73 69 6e 63 65 20 69 74 | 20 66 61 6c 6c 73 20 69 |since it| falls i|
|00005090| 6e 20 74 68 65 20 38 20 | 78 20 38 20 62 6f 78 2c |n the 8 |x 8 box,|
|000050a0| 20 6e 6f 20 66 75 72 74 | 68 65 72 20 72 65 64 75 | no furt|her redu|
|000050b0| 63 74 69 6f 6e 20 69 73 | 20 6e 65 63 65 73 73 61 |ction is| necessa|
|000050c0| 72 79 2e 20 53 74 65 70 | 20 36 20 61 64 64 73 20 |ry. Step| 6 adds |
|000050d0| 74 68 65 20 65 69 67 68 | 74 68 20 61 6e 64 20 6c |the eigh|th and l|
|000050e0| 61 73 74 20 63 6f 6c 6f | 72 2e 20 49 74 20 64 6f |ast colo|r. It do|
|000050f0| 65 73 6e d5 74 20 66 61 | 6c 6c 20 69 6e 74 6f 20 |esn.t fa|ll into |
|00005100| 61 6e 20 65 78 69 73 74 | 69 6e 67 20 6e 6f 64 65 |an exist|ing node|
|00005110| 2c 20 73 6f 20 61 20 72 | 65 64 75 63 74 69 6f 6e |, so a r|eduction|
|00005120| 20 69 73 20 64 6f 6e 65 | 20 61 6e 64 20 61 6e 6f | is done| and ano|
|00005130| 74 68 65 72 20 38 20 78 | 20 38 20 62 6f 78 20 69 |ther 8 x| 8 box i|
|00005140| 73 20 66 6f 72 6d 65 64 | 2e 20 41 73 20 74 68 65 |s formed|. As the|
|00005150| 72 65 20 61 72 65 20 6e | 6f 20 6d 6f 72 65 20 63 |re are n|o more c|
|00005160| 6f 6c 6f 72 73 20 69 6e | 20 74 68 65 20 69 6d 61 |olors in| the ima|
|00005170| 67 65 2c 20 74 68 65 20 | 77 65 69 67 68 74 65 64 |ge, the |weighted|
|00005180| 20 61 76 65 72 61 67 65 | 20 6f 66 20 74 68 65 20 | average| of the |
|00005190| 63 6f 6c 6f 72 73 20 69 | 6e 20 65 61 63 68 20 6f |colors i|n each o|
|000051a0| 66 20 74 68 65 20 62 6f | 78 65 73 20 69 73 20 72 |f the bo|xes is r|
|000051b0| 65 74 75 72 6e 65 64 20 | 61 6e 64 20 77 65 d5 72 |eturned |and we.r|
|000051c0| 65 20 64 6f 6e 65 2e 0d | 45 78 74 65 6e 64 69 6e |e done..|Extendin|
|000051d0| 67 20 74 68 69 73 20 61 | 6c 67 6f 72 69 74 68 6d |g this a|lgorithm|
|000051e0| 20 74 6f 20 77 6f 72 6b | 20 69 6e 20 74 68 72 65 | to work| in thre|
|000051f0| 65 20 64 69 6d 65 6e 73 | 69 6f 6e 73 20 72 61 74 |e dimens|ions rat|
|00005200| 68 65 72 20 74 68 61 6e | 20 74 77 6f 20 69 73 20 |her than| two is |
|00005210| 65 61 73 79 2e 20 54 68 | 65 20 64 65 74 61 69 6c |easy. Th|e detail|
|00005220| 73 20 6f 66 20 74 68 65 | 20 69 6d 70 6c 65 6d 65 |s of the| impleme|
|00005230| 6e 74 61 74 69 6f 6e 20 | 61 72 65 20 69 6e 20 74 |ntation |are in t|
|00005240| 68 65 20 73 6f 75 72 63 | 65 20 63 6f 64 65 2c 20 |he sourc|e code, |
|00005250| 77 68 69 63 68 20 63 61 | 6e 20 62 65 20 66 6f 75 |which ca|n be fou|
|00005260| 6e 64 20 6f 6e 20 74 68 | 65 20 44 65 76 65 6c 6f |nd on th|e Develo|
|00005270| 70 65 72 20 43 44 20 53 | 65 72 69 65 73 20 64 69 |per CD S|eries di|
|00005280| 73 63 2e 20 4f 6e 63 65 | 20 79 6f 75 d5 76 65 20 |sc. Once| you.ve |
|00005290| 73 74 75 64 69 65 64 20 | 74 68 69 73 20 73 6f 75 |studied |this sou|
|000052a0| 72 63 65 20 63 6f 64 65 | 20 79 6f 75 20 6d 61 79 |rce code| you may|
|000052b0| 20 77 61 6e 74 20 74 6f | 20 77 72 69 74 65 20 79 | want to| write y|
|000052c0| 6f 75 72 20 6f 77 6e 20 | 63 6f 6d 70 6c 65 74 65 |our own |complete|
|000052d0| 6c 79 20 64 69 66 66 65 | 72 65 6e 74 20 63 6f 6c |ly diffe|rent col|
|000052e0| 6f 72 20 73 65 6c 65 63 | 74 69 6f 6e 20 61 6c 67 |or selec|tion alg|
|000052f0| 6f 72 69 74 68 6d 3b 20 | 43 68 61 70 74 65 72 20 |orithm; |Chapter |
|00005300| 31 38 20 6f 66 20 49 6e | 73 69 64 65 20 4d 61 63 |18 of In|side Mac|
|00005310| 69 6e 74 6f 73 68 20 56 | 6f 6c 75 6d 65 20 56 49 |intosh V|olume VI|
|00005320| 20 66 75 6c 6c 79 20 64 | 65 73 63 72 69 62 65 73 | fully d|escribes|
|00005330| 20 68 6f 77 20 74 6f 20 | 64 6f 20 74 68 69 73 2e | how to |do this.|
|00005340| 20 0d 41 44 44 49 54 49 | 4f 4e 41 4c 20 41 50 50 | .ADDITI|ONAL APP|
|00005350| 4c 49 43 41 54 49 4f 4e | 20 43 4f 44 45 0d 49 6e |LICATION| CODE.In|
|00005360| 20 61 64 64 69 74 69 6f | 6e 20 74 6f 20 74 68 65 | additio|n to the|
|00005370| 20 63 6f 64 65 20 66 6f | 72 20 74 68 65 20 6f 63 | code fo|r the oc|
|00005380| 74 72 65 65 20 61 6c 67 | 6f 72 69 74 68 6d 20 69 |tree alg|orithm i|
|00005390| 74 73 65 6c 66 2c 20 77 | 65 d5 76 65 20 73 75 70 |tself, w|e.ve sup|
|000053a0| 70 6c 69 65 64 20 63 6f | 64 65 20 6f 6e 20 74 68 |plied co|de on th|
|000053b0| 65 20 43 44 20 66 6f 72 | 20 61 20 63 72 75 64 65 |e CD for| a crude|
|000053c0| 20 74 65 73 74 20 61 70 | 70 6c 69 63 61 74 69 6f | test ap|plicatio|
|000053d0| 6e 20 74 68 61 74 20 64 | 65 6d 6f 6e 73 74 72 61 |n that d|emonstra|
|000053e0| 74 65 73 20 68 6f 77 20 | 74 6f 20 61 70 70 6c 79 |tes how |to apply|
|000053f0| 20 62 6f 74 68 20 74 68 | 65 20 70 6f 70 75 6c 61 | both th|e popula|
|00005400| 72 20 61 6e 64 20 6d 65 | 64 69 61 6e 20 6d 65 74 |r and me|dian met|
|00005410| 68 6f 64 73 20 61 73 20 | 77 65 6c 6c 20 61 73 20 |hods as |well as |
|00005420| 74 68 65 20 6f 63 74 72 | 65 65 20 6d 65 74 68 6f |the octr|ee metho|
|00005430| 64 20 74 6f 20 61 20 70 | 69 63 74 75 72 65 20 63 |d to a p|icture c|
|00005440| 6f 6e 74 61 69 6e 65 64 | 20 69 6e 20 61 20 50 49 |ontained| in a PI|
|00005450| 43 54 20 66 69 6c 65 2e | 20 54 68 65 20 74 65 73 |CT file.| The tes|
|00005460| 74 20 61 70 70 6c 69 63 | 61 74 69 6f 6e 20 68 61 |t applic|ation ha|
|00005470| 73 20 61 20 76 65 72 79 | 20 73 69 6d 70 6c 65 20 |s a very| simple |
|00005480| 75 73 65 72 20 69 6e 74 | 65 72 66 61 63 65 20 74 |user int|erface t|
|00005490| 68 61 74 20 61 6c 6c 6f | 77 73 20 79 6f 75 20 74 |hat allo|ws you t|
|000054a0| 6f 20 6f 70 65 6e 20 61 | 6e 79 20 50 49 43 54 20 |o open a|ny PICT |
|000054b0| 66 69 6c 65 20 61 6e 64 | 20 73 65 65 20 77 68 61 |file and| see wha|
|000054c0| 74 20 69 74 20 6c 6f 6f | 6b 73 20 6c 69 6b 65 20 |t it loo|ks like |
|000054d0| 75 73 69 6e 67 20 74 68 | 65 20 73 65 74 20 6f 66 |using th|e set of|
|000054e0| 20 63 6f 6c 6f 72 73 20 | 72 65 74 75 72 6e 65 64 | colors |returned|
|000054f0| 20 62 79 20 74 68 65 20 | 70 6f 70 75 6c 61 72 2c | by the |popular,|
|00005500| 20 6d 65 64 69 61 6e 2c | 20 61 6e 64 20 6f 63 74 | median,| and oct|
|00005510| 72 65 65 20 61 6c 67 6f | 72 69 74 68 6d 73 2c 20 |ree algo|rithms, |
|00005520| 61 73 20 77 65 6c 6c 20 | 61 73 20 74 68 65 20 73 |as well |as the s|
|00005530| 74 61 6e 64 61 72 64 20 | 73 79 73 74 65 6d 20 63 |tandard |system c|
|00005540| 6f 6c 6f 72 20 74 61 62 | 6c 65 2e 0d 54 68 65 20 |olor tab|le..The |
|00005550| 73 6f 75 72 63 65 20 63 | 6f 64 65 20 66 6f 72 20 |source c|ode for |
|00005560| 74 68 69 73 20 61 70 70 | 6c 69 63 61 74 69 6f 6e |this app|lication|
|00005570| 20 73 68 6f 77 73 20 68 | 6f 77 20 74 6f 20 61 73 | shows h|ow to as|
|00005580| 73 6f 63 69 61 74 65 20 | 74 68 65 20 63 6f 6c 6f |sociate |the colo|
|00005590| 72 20 69 6e 66 6f 72 6d | 61 74 69 6f 6e 20 74 68 |r inform|ation th|
|000055a0| 61 74 20 50 69 63 74 75 | 72 65 20 55 74 69 6c 69 |at Pictu|re Utili|
|000055b0| 74 69 65 73 20 72 65 74 | 75 72 6e 73 20 77 69 74 |ties ret|urns wit|
|000055c0| 68 20 77 69 6e 64 6f 77 | 73 2c 20 61 6e 64 20 69 |h window|s, and i|
|000055d0| 74 20 61 6c 73 6f 20 63 | 6f 6e 74 61 69 6e 73 20 |t also c|ontains |
|000055e0| 73 65 76 65 72 61 6c 20 | 75 73 65 66 75 6c 20 72 |several |useful r|
|000055f0| 6f 75 74 69 6e 65 73 20 | 66 6f 72 20 6d 61 6e 61 |outines |for mana|
|00005600| 67 69 6e 67 20 70 69 63 | 74 75 72 65 73 20 73 74 |ging pic|tures st|
|00005610| 6f 72 65 64 20 6f 6e 20 | 64 69 73 6b 2e 20 54 68 |ored on |disk. Th|
|00005620| 65 73 65 20 72 6f 75 74 | 69 6e 65 73 20 61 6c 6c |ese rout|ines all|
|00005630| 6f 77 20 79 6f 75 20 74 | 6f 20 74 72 65 61 74 20 |ow you t|o treat |
|00005640| d2 64 69 73 6b 20 70 69 | 63 74 75 72 65 73 d3 20 |.disk pi|ctures. |
|00005650| 61 73 20 6f 62 6a 65 63 | 74 73 20 74 68 61 74 20 |as objec|ts that |
|00005660| 63 61 6e 20 65 61 73 69 | 6c 79 20 62 65 20 70 61 |can easi|ly be pa|
|00005670| 73 73 65 64 20 61 72 6f | 75 6e 64 20 74 6f 20 76 |ssed aro|und to v|
|00005680| 61 72 69 6f 75 73 20 72 | 6f 75 74 69 6e 65 73 2c |arious r|outines,|
|00005690| 20 64 72 61 77 6e 2c 20 | 70 72 6f 66 69 6c 65 64 | drawn, |profiled|
|000056a0| 20 28 75 73 69 6e 67 20 | 50 69 63 74 75 72 65 20 | (using |Picture |
|000056b0| 55 74 69 6c 69 74 69 65 | 73 29 2c 20 61 6e 64 20 |Utilitie|s), and |
|000056c0| 65 76 65 6e 20 63 61 63 | 68 65 64 20 69 6e 20 6d |even cac|hed in m|
|000056d0| 65 6d 6f 72 79 20 69 66 | 20 74 68 65 72 65 d5 73 |emory if| there.s|
|000056e0| 20 73 70 61 63 65 20 74 | 6f 20 64 6f 20 73 6f 2e | space t|o do so.|
|000056f0| 20 54 61 6b 65 20 61 20 | 6c 6f 6f 6b 20 61 74 20 | Take a |look at |
|00005700| 74 68 65 20 61 63 74 75 | 61 6c 20 73 6f 75 72 63 |the actu|al sourc|
|00005710| 65 20 66 6f 72 20 74 68 | 65 20 64 65 74 61 69 6c |e for th|e detail|
|00005720| 73 20 6f 6e 20 61 6c 6c | 20 74 68 69 73 2e 0d 4f |s on all| this..O|
|00005730| 75 72 20 74 65 73 74 20 | 61 70 70 6c 69 63 61 74 |ur test |applicat|
|00005740| 69 6f 6e 20 64 6f 65 73 | 20 6e 6f 74 20 61 74 74 |ion does| not att|
|00005750| 65 6d 70 74 20 74 6f 20 | 64 65 6d 6f 6e 73 74 72 |empt to |demonstr|
|00005760| 61 74 65 20 68 6f 77 20 | 74 6f 20 75 73 65 20 50 |ate how |to use P|
|00005770| 69 63 74 75 72 65 20 55 | 74 69 6c 69 74 69 65 73 |icture U|tilities|
|00005780| 20 74 6f 20 70 72 6f 66 | 69 6c 65 20 6d 75 6c 74 | to prof|ile mult|
|00005790| 69 70 6c 65 20 70 69 63 | 74 75 72 65 73 20 61 6e |iple pic|tures an|
|000057a0| 64 20 70 69 78 4d 61 70 | 73 3b 20 73 65 65 20 49 |d pixMap|s; see I|
|000057b0| 6e 73 69 64 65 20 4d 61 | 63 69 6e 74 6f 73 68 20 |nside Ma|cintosh |
|000057c0| 56 6f 6c 75 6d 65 20 56 | 49 20 66 6f 72 20 61 20 |Volume V|I for a |
|000057d0| 63 6f 6d 70 6c 65 74 65 | 20 65 78 70 6c 61 6e 61 |complete| explana|
|000057e0| 74 69 6f 6e 20 6f 66 20 | 68 6f 77 20 74 6f 20 64 |tion of |how to d|
|000057f0| 6f 20 74 68 69 73 2e 0d | 52 4f 4f 4d 20 46 4f 52 |o this..|ROOM FOR|
|00005800| 20 49 4d 50 52 4f 56 45 | 4d 45 4e 54 0d 46 72 6f | IMPROVE|MENT.Fro|
|00005810| 6d 20 74 68 65 20 61 6c | 67 6f 72 69 74 68 6d 73 |m the al|gorithms|
|00005820| 2c 20 69 74 20 73 65 65 | 6d 73 20 61 73 20 74 68 |, it see|ms as th|
|00005830| 6f 75 67 68 20 74 68 65 | 20 6d 65 64 69 61 6e 20 |ough the| median |
|00005840| 61 6e 64 20 6f 63 74 72 | 65 65 20 6d 65 74 68 6f |and octr|ee metho|
|00005850| 64 73 20 73 68 6f 75 6c | 64 20 70 72 6f 64 75 63 |ds shoul|d produc|
|00005860| 65 20 61 6e 20 65 78 63 | 65 6c 6c 65 6e 74 20 73 |e an exc|ellent s|
|00005870| 65 74 20 6f 66 20 63 6f | 6c 6f 72 73 20 77 69 74 |et of co|lors wit|
|00005880| 68 20 77 68 69 63 68 20 | 74 6f 20 64 69 73 70 6c |h which |to displ|
|00005890| 61 79 20 61 6e 79 20 69 | 6d 61 67 65 2e 20 55 6e |ay any i|mage. Un|
|000058a0| 66 6f 72 74 75 6e 61 74 | 65 6c 79 2c 20 62 6f 74 |fortunat|ely, bot|
|000058b0| 68 20 61 6c 67 6f 72 69 | 74 68 6d 73 20 66 61 6c |h algori|thms fal|
|000058c0| 6c 20 73 6f 6d 65 77 68 | 61 74 20 73 68 6f 72 74 |l somewh|at short|
|000058d0| 20 6f 66 20 74 68 69 73 | 20 67 6f 61 6c 2c 20 65 | of this| goal, e|
|000058e0| 73 70 65 63 69 61 6c 6c | 79 20 77 69 74 68 20 69 |speciall|y with i|
|000058f0| 6d 61 67 65 73 20 74 68 | 61 74 20 68 61 76 65 20 |mages th|at have |
|00005900| 61 20 66 61 69 72 6c 79 | 20 77 65 6c 6c 20 64 69 |a fairly| well di|
|00005910| 73 70 65 72 73 65 64 20 | 73 65 74 20 6f 66 20 63 |spersed |set of c|
|00005920| 6f 6c 6f 72 73 2e 0d 57 | 65 20 63 61 6e 20 74 68 |olors..W|e can th|
|00005930| 69 6e 6b 20 6f 66 20 73 | 65 76 65 72 61 6c 20 61 |ink of s|everal a|
|00005940| 72 65 61 73 20 77 68 65 | 72 65 20 62 6f 74 68 20 |reas whe|re both |
|00005950| 63 6f 75 6c 64 20 62 65 | 20 69 6d 70 72 6f 76 65 |could be| improve|
|00005960| 64 2e 20 46 69 72 73 74 | 2c 20 62 6f 74 68 20 61 |d. First|, both a|
|00005970| 6c 67 6f 72 69 74 68 6d | 73 20 77 65 69 67 68 20 |lgorithm|s weigh |
|00005980| 74 68 65 20 72 65 64 2c | 20 67 72 65 65 6e 2c 20 |the red,| green, |
|00005990| 61 6e 64 20 62 6c 75 65 | 20 61 78 65 73 20 65 71 |and blue| axes eq|
|000059a0| 75 61 6c 6c 79 2e 20 41 | 73 20 69 74 20 74 75 72 |ually. A|s it tur|
|000059b0| 6e 73 20 6f 75 74 2c 20 | 74 68 65 20 65 79 65 20 |ns out, |the eye |
|000059c0| 64 6f 65 73 20 74 68 65 | 20 62 65 73 74 20 6a 6f |does the| best jo|
|000059d0| 62 20 6f 66 20 70 65 72 | 63 65 69 76 69 6e 67 20 |b of per|ceiving |
|000059e0| 67 72 65 65 6e 20 61 6e | 64 20 61 20 72 65 6c 61 |green an|d a rela|
|000059f0| 74 69 76 65 6c 79 20 70 | 6f 6f 72 65 72 20 6a 6f |tively p|oorer jo|
|00005a00| 62 20 6f 66 20 70 65 72 | 63 65 69 76 69 6e 67 20 |b of per|ceiving |
|00005a10| 62 6c 75 65 2e 20 50 65 | 72 68 61 70 73 20 64 69 |blue. Pe|rhaps di|
|00005a20| 66 66 65 72 65 6e 74 20 | 77 65 69 67 68 74 73 20 |fferent |weights |
|00005a30| 63 6f 75 6c 64 20 62 65 | 20 61 73 73 69 67 6e 65 |could be| assigne|
|00005a40| 64 20 74 6f 20 74 68 65 | 20 61 78 65 73 20 74 6f |d to the| axes to|
|00005a50| 20 63 6f 6d 70 65 6e 73 | 61 74 65 20 66 6f 72 20 | compens|ate for |
|00005a60| 74 68 69 73 20 71 75 69 | 72 6b 20 6f 66 20 68 75 |this qui|rk of hu|
|00005a70| 6d 61 6e 20 70 65 72 63 | 65 70 74 69 6f 6e 2e 20 |man perc|eption. |
|00005a80| 41 6e 20 61 64 76 61 6e | 63 65 64 20 63 6f 6c 6f |An advan|ced colo|
|00005a90| 72 20 73 65 6c 65 63 74 | 69 6f 6e 20 6d 65 74 68 |r select|ion meth|
|00005aa0| 6f 64 20 63 6f 75 6c 64 | 20 74 61 6b 65 20 69 6e |od could| take in|
|00005ab0| 74 6f 20 61 63 63 6f 75 | 6e 74 20 74 68 65 20 66 |to accou|nt the f|
|00005ac0| 61 63 74 20 74 68 61 74 | 20 65 76 65 6e 20 77 69 |act that| even wi|
|00005ad0| 74 68 69 6e 20 6f 6e 65 | 20 63 6f 6c 6f 72 20 61 |thin one| color a|
|00005ae0| 78 69 73 2c 20 74 68 65 | 20 65 79 65 20 64 6f 65 |xis, the| eye doe|
|00005af0| 73 20 6e 6f 74 20 70 65 | 72 63 65 69 76 65 20 74 |s not pe|rceive t|
|00005b00| 68 65 20 63 6f 6c 6f 72 | 20 28 69 6e 74 65 6e 73 |he color| (intens|
|00005b10| 69 74 79 20 61 6e 64 20 | 73 61 74 75 72 61 74 69 |ity and |saturati|
|00005b20| 6f 6e 29 20 75 6e 69 66 | 6f 72 6d 6c 79 2c 20 61 |on) unif|ormly, a|
|00005b30| 6e 64 20 63 6f 75 6c 64 | 20 63 6f 6d 70 65 6e 73 |nd could| compens|
|00005b40| 61 74 65 20 66 6f 72 20 | 76 61 72 69 61 74 69 6f |ate for |variatio|
|00005b50| 6e 20 69 6e 20 74 68 65 | 20 67 61 6d 6d 61 20 66 |n in the| gamma f|
|00005b60| 75 6e 63 74 69 6f 6e 20 | 6f 66 20 65 61 63 68 20 |unction |of each |
|00005b70| 6d 6f 6e 69 74 6f 72 20 | 61 73 20 77 65 6c 6c 2e |monitor |as well.|
|00005b80| 0d 53 65 63 6f 6e 64 2c | 20 69 6e 20 62 6f 74 68 |.Second,| in both|
|00005b90| 20 6d 65 74 68 6f 64 73 | 20 74 68 65 20 63 6f 6c | methods| the col|
|00005ba0| 6f 72 73 20 69 6e 20 74 | 68 65 20 66 69 6e 61 6c |ors in t|he final|
|00005bb0| 20 62 6f 78 65 73 20 61 | 72 65 20 61 76 65 72 61 | boxes a|re avera|
|00005bc0| 67 65 64 2e 20 57 68 69 | 6c 65 20 74 68 69 73 20 |ged. Whi|le this |
|00005bd0| 70 72 6f 64 75 63 65 73 | 20 74 68 65 20 63 6f 6c |produces| the col|
|00005be0| 6f 72 20 74 68 61 74 20 | 6d 6f 73 74 20 61 63 63 |or that |most acc|
|00005bf0| 75 72 61 74 65 6c 79 20 | 72 65 70 72 65 73 65 6e |urately |represen|
|00005c00| 74 73 20 65 61 63 68 20 | 62 6f 78 2c 20 69 74 20 |ts each |box, it |
|00005c10| 6e 65 63 65 73 73 61 72 | 69 6c 79 20 6c 65 61 76 |necessar|ily leav|
|00005c20| 65 73 20 73 6f 6d 65 20 | 63 6f 6c 6f 72 73 20 75 |es some |colors u|
|00005c30| 6e 72 65 61 63 68 61 62 | 6c 65 2c 20 65 76 65 6e |nreachab|le, even|
|00005c40| 20 62 79 20 64 69 74 68 | 65 72 69 6e 67 2e 20 41 | by dith|ering. A|
|00005c50| 20 62 65 74 74 65 72 20 | 63 68 6f 69 63 65 20 6f | better |choice o|
|00005c60| 66 20 63 6f 6c 6f 72 20 | 6d 69 67 68 74 20 62 65 |f color |might be|
|00005c70| 20 74 68 65 20 63 6f 72 | 6e 65 72 20 6f 66 20 74 | the cor|ner of t|
|00005c80| 68 65 20 66 69 6e 61 6c | 20 62 6f 78 20 74 68 61 |he final| box tha|
|00005c90| 74 d5 73 20 66 61 72 74 | 68 65 73 74 20 61 77 61 |t.s fart|hest awa|
|00005ca0| 79 20 66 72 6f 6d 20 74 | 68 65 20 63 65 6e 74 65 |y from t|he cente|
|00005cb0| 72 20 6f 66 20 74 68 65 | 20 52 47 42 20 63 75 62 |r of the| RGB cub|
|00005cc0| 65 2e 20 54 68 69 73 20 | 77 6f 75 6c 64 20 61 73 |e. This |would as|
|00005cd0| 73 75 72 65 20 74 68 61 | 74 20 61 6c 6c 20 74 68 |sure tha|t all th|
|00005ce0| 65 20 63 6f 6c 6f 72 73 | 20 69 6e 20 74 68 65 20 |e colors| in the |
|00005cf0| 69 6d 61 67 65 20 77 6f | 75 6c 64 20 62 65 20 77 |image wo|uld be w|
|00005d00| 69 74 68 69 6e 20 74 68 | 65 20 63 75 62 65 20 6f |ithin th|e cube o|
|00005d10| 66 20 63 6f 6c 6f 72 73 | 20 64 65 66 69 6e 65 64 |f colors| defined|
|00005d20| 20 62 79 20 74 68 65 20 | 70 61 6c 65 74 74 65 20 | by the |palette |
|00005d30| 75 73 65 64 20 74 6f 20 | 72 65 70 72 65 73 65 6e |used to |represen|
|00005d40| 74 20 74 68 65 20 69 6d | 61 67 65 2e 0d 54 68 65 |t the im|age..The|
|00005d50| 20 6d 65 64 69 61 6e 20 | 6d 65 74 68 6f 64 20 69 | median |method i|
|00005d60| 73 6e d5 74 20 61 20 72 | 65 61 6c 69 73 74 69 63 |sn.t a r|ealistic|
|00005d70| 20 63 61 6e 64 69 64 61 | 74 65 20 66 6f 72 20 69 | candida|te for i|
|00005d80| 6d 70 72 6f 76 65 6d 65 | 6e 74 20 73 69 6e 63 65 |mproveme|nt since|
|00005d90| 20 69 74 d5 73 20 62 75 | 69 6c 74 20 69 6e 74 6f | it.s bu|ilt into|
|00005da0| 20 74 68 65 20 50 69 63 | 74 75 72 65 20 55 74 69 | the Pic|ture Uti|
|00005db0| 6c 69 74 69 65 73 20 50 | 61 63 6b 61 67 65 2e 20 |lities P|ackage. |
|00005dc0| 4f 6e 20 74 68 65 20 6f | 74 68 65 72 20 68 61 6e |On the o|ther han|
|00005dd0| 64 2c 20 77 65 d5 72 65 | 20 70 72 6f 76 69 64 69 |d, we.re| providi|
|00005de0| 6e 67 20 79 6f 75 20 77 | 69 74 68 20 74 68 65 20 |ng you w|ith the |
|00005df0| 66 75 6c 6c 20 73 6f 75 | 72 63 65 20 63 6f 64 65 |full sou|rce code|
|00005e00| 20 66 6f 72 20 74 68 65 | 20 6f 63 74 72 65 65 20 | for the| octree |
|00005e10| 6d 65 74 68 6f 64 2c 20 | 73 6f 20 79 6f 75 d5 72 |method, |so you.r|
|00005e20| 65 20 66 72 65 65 20 74 | 6f 20 6d 6f 64 69 66 79 |e free t|o modify|
|00005e30| 20 69 74 2e 20 53 69 6e | 63 65 20 74 68 61 74 d5 | it. Sin|ce that.|
|00005e40| 73 20 74 68 65 20 63 61 | 73 65 2c 20 77 65 d5 6c |s the ca|se, we.l|
|00005e50| 6c 20 73 75 67 67 65 73 | 74 20 61 20 66 65 77 20 |l sugges|t a few |
|00005e60| 6f 74 68 65 72 20 74 68 | 69 6e 67 73 20 74 68 61 |other th|ings tha|
|00005e70| 74 20 63 6f 75 6c 64 20 | 62 65 20 69 6d 70 72 6f |t could |be impro|
|00005e80| 76 65 64 2e 0d 54 68 65 | 20 6d 6f 73 74 20 69 6d |ved..The| most im|
|00005e90| 70 6f 72 74 61 6e 74 20 | 70 61 72 74 20 6f 66 20 |portant |part of |
|00005ea0| 74 68 65 20 6f 63 74 72 | 65 65 20 6d 65 74 68 6f |the octr|ee metho|
|00005eb0| 64 20 69 73 20 64 65 74 | 65 72 6d 69 6e 69 6e 67 |d is det|ermining|
|00005ec0| 20 77 68 69 63 68 20 6e | 6f 64 65 73 20 69 6e 20 | which n|odes in |
|00005ed0| 74 68 65 20 74 72 65 65 | 20 74 6f 20 72 65 64 75 |the tree| to redu|
|00005ee0| 63 65 20 77 68 65 6e 20 | 74 68 65 20 6d 61 78 69 |ce when |the maxi|
|00005ef0| 6d 75 6d 20 6e 75 6d 62 | 65 72 20 6f 66 20 63 6f |mum numb|er of co|
|00005f00| 6c 6f 72 73 20 68 61 73 | 20 62 65 65 6e 20 72 65 |lors has| been re|
|00005f10| 61 63 68 65 64 2e 20 54 | 68 65 20 61 6c 67 6f 72 |ached. T|he algor|
|00005f20| 69 74 68 6d 20 77 65 20 | 75 73 65 20 69 6e 20 6f |ithm we |use in o|
|00005f30| 75 72 20 73 61 6d 70 6c | 65 20 63 6f 64 65 20 69 |ur sampl|e code i|
|00005f40| 73 20 6d 75 63 68 20 74 | 6f 6f 20 73 69 6d 70 6c |s much t|oo simpl|
|00005f50| 65 3b 20 77 65 20 73 69 | 6d 70 6c 79 20 73 63 61 |e; we si|mply sca|
|00005f60| 6e 20 74 68 72 6f 75 67 | 68 20 61 6c 6c 20 74 68 |n throug|h all th|
|00005f70| 65 20 6e 6f 64 65 73 20 | 61 74 20 74 68 65 20 64 |e nodes |at the d|
|00005f80| 65 65 70 65 73 74 20 6c | 65 76 65 6c 20 6c 6f 6f |eepest l|evel loo|
|00005f90| 6b 69 6e 67 20 66 6f 72 | 20 6f 6e 65 20 74 68 61 |king for| one tha|
|00005fa0| 74 20 68 61 73 20 74 77 | 6f 20 6f 72 20 6d 6f 72 |t has tw|o or mor|
|00005fb0| 65 20 63 6f 6c 6f 72 73 | 20 68 61 6e 67 69 6e 67 |e colors| hanging|
|00005fc0| 20 6f 66 66 20 69 74 2e | 20 54 68 65 6e 20 69 66 | off it.| Then if|
|00005fd0| 20 77 65 20 64 6f 6e d5 | 74 20 66 69 6e 64 20 61 | we don.|t find a|
|00005fe0| 6e 79 20 73 75 63 68 20 | 6e 6f 64 65 73 20 61 74 |ny such |nodes at|
|00005ff0| 20 74 68 65 20 64 65 65 | 70 65 73 74 20 6c 65 76 | the dee|pest lev|
|00006000| 65 6c 2c 20 77 65 20 6d | 6f 76 65 20 75 70 20 61 |el, we m|ove up a|
|00006010| 20 6c 65 76 65 6c 20 61 | 6e 64 20 6c 6f 6f 6b 20 | level a|nd look |
|00006020| 66 6f 72 20 6f 6e 65 73 | 20 74 68 61 74 20 68 61 |for ones| that ha|
|00006030| 76 65 20 74 77 6f 20 6f | 72 20 6d 6f 72 65 20 6e |ve two o|r more n|
|00006040| 6f 64 65 73 20 68 61 6e | 67 69 6e 67 20 6f 66 66 |odes han|ging off|
|00006050| 20 74 68 65 6d 2e 0d 4f | 6e 65 20 62 65 74 74 65 | them..O|ne bette|
|00006060| 72 20 61 70 70 72 6f 61 | 63 68 20 77 6f 75 6c 64 |r approa|ch would|
|00006070| 20 62 65 20 74 6f 20 72 | 65 64 75 63 65 20 6e 6f | be to r|educe no|
|00006080| 64 65 73 20 74 68 61 74 | 20 68 61 76 65 20 74 68 |des that| have th|
|00006090| 65 20 6d 6f 73 74 20 64 | 69 73 63 72 65 74 65 20 |e most d|iscrete |
|000060a0| 63 6f 6c 6f 72 73 20 68 | 61 6e 67 69 6e 67 20 6f |colors h|anging o|
|000060b0| 66 66 20 74 68 65 6d 3b | 20 74 68 69 73 20 77 6f |ff them;| this wo|
|000060c0| 75 6c 64 20 74 65 6e 64 | 20 74 6f 20 62 6c 65 6e |uld tend| to blen|
|000060d0| 64 20 73 69 6d 69 6c 61 | 72 20 73 68 61 64 65 73 |d simila|r shades|
|000060e0| 20 69 6e 74 6f 20 61 20 | 73 69 6e 67 6c 65 20 63 | into a |single c|
|000060f0| 6f 6c 6f 72 2c 20 77 68 | 69 6c 65 20 70 72 65 73 |olor, wh|ile pres|
|00006100| 65 72 76 69 6e 67 20 d2 | 66 72 69 6e 67 65 d3 20 |erving .|fringe. |
|00006110| 63 6f 6c 6f 72 73 2e 20 | 41 6e 6f 74 68 65 72 20 |colors. |Another |
|00006120| 61 70 70 72 6f 61 63 68 | 20 77 6f 75 6c 64 20 62 |approach| would b|
|00006130| 65 20 74 6f 20 72 65 64 | 75 63 65 20 74 68 65 20 |e to red|uce the |
|00006140| 6e 6f 64 65 73 20 74 68 | 61 74 20 68 61 76 65 20 |nodes th|at have |
|00006150| 74 68 65 20 6d 6f 73 74 | 20 6f 63 63 75 72 72 65 |the most| occurre|
|00006160| 6e 63 65 73 20 6f 66 20 | 63 6f 6c 6f 72 73 20 68 |nces of |colors h|
|00006170| 61 6e 67 69 6e 67 20 6f | 66 66 20 74 68 65 6d 20 |anging o|ff them |
|00006180| 73 6f 20 74 68 61 74 20 | 73 6d 61 6c 6c 20 73 70 |so that |small sp|
|00006190| 6c 61 73 68 65 73 20 6f | 66 20 63 6f 6c 6f 72 20 |lashes o|f color |
|000061a0| 77 6f 75 6c 64 20 6e 6f | 74 20 6c 6f 73 65 20 74 |would no|t lose t|
|000061b0| 68 65 69 72 20 64 69 73 | 74 69 6e 63 74 6e 65 73 |heir dis|tinctnes|
|000061c0| 73 2e 20 0d 4f 66 20 63 | 6f 75 72 73 65 2c 20 69 |s. .Of c|ourse, i|
|000061d0| 66 20 69 74 d5 73 20 69 | 6d 70 6f 72 74 61 6e 74 |f it.s i|mportant|
|000061e0| 20 74 6f 20 70 72 65 73 | 65 72 76 65 20 73 75 62 | to pres|erve sub|
|000061f0| 74 6c 65 20 73 68 61 64 | 65 73 20 69 6e 20 74 68 |tle shad|es in th|
|00006200| 65 20 6d 61 69 6e 20 61 | 72 65 61 73 20 6f 66 20 |e main a|reas of |
|00006210| 74 68 65 20 70 69 63 74 | 75 72 65 20 61 6e 64 20 |the pict|ure and |
|00006220| 69 74 d5 73 20 4f 4b 20 | 66 6f 72 20 66 72 69 6e |it.s OK |for frin|
|00006230| 67 65 20 63 6f 6c 6f 72 | 73 20 74 6f 20 62 65 20 |ge color|s to be |
|00006240| 64 72 61 73 74 69 63 61 | 6c 6c 79 20 6d 6f 64 69 |drastica|lly modi|
|00006250| 66 69 65 64 2c 20 74 68 | 65 20 70 72 65 76 69 6f |fied, th|e previo|
|00006260| 75 73 6c 79 20 6d 65 6e | 74 69 6f 6e 65 64 20 69 |usly men|tioned i|
|00006270| 6d 70 72 6f 76 65 6d 65 | 6e 74 73 20 63 6f 75 6c |mproveme|nts coul|
|00006280| 64 20 62 65 20 72 65 76 | 65 72 73 65 64 20 74 6f |d be rev|ersed to|
|00006290| 20 61 6c 77 61 79 73 20 | 72 65 64 75 63 65 20 74 | always |reduce t|
|000062a0| 68 65 20 6e 6f 64 65 73 | 20 77 69 74 68 20 74 68 |he nodes| with th|
|000062b0| 65 20 66 65 77 65 73 74 | 20 64 69 73 63 72 65 74 |e fewest| discret|
|000062c0| 65 20 63 6f 6c 6f 72 73 | 20 6f 72 20 74 68 65 20 |e colors| or the |
|000062d0| 6e 6f 64 65 73 20 77 69 | 74 68 20 74 68 65 20 66 |nodes wi|th the f|
|000062e0| 65 77 65 73 74 20 6f 63 | 63 75 72 72 65 6e 63 65 |ewest oc|currence|
|000062f0| 73 2e 20 41 20 67 6f 6f | 64 20 67 65 6e 65 72 61 |s. A goo|d genera|
|00006300| 6c 20 61 6c 67 6f 72 69 | 74 68 6d 20 77 6f 75 6c |l algori|thm woul|
|00006310| 64 20 70 72 6f 62 61 62 | 6c 79 20 74 72 79 20 74 |d probab|ly try t|
|00006320| 6f 20 69 6e 63 6f 72 70 | 6f 72 61 74 65 20 62 6f |o incorp|orate bo|
|00006330| 74 68 20 6f 66 20 74 68 | 65 73 65 20 65 66 66 65 |th of th|ese effe|
|00006340| 63 74 73 20 62 79 20 68 | 61 76 69 6e 67 20 61 6e |cts by h|aving an|
|00006350| 20 6f 63 63 75 72 72 65 | 6e 63 65 20 74 68 72 65 | occurre|nce thre|
|00006360| 73 68 6f 6c 64 3b 20 63 | 6f 6c 6f 72 73 20 74 68 |shold; c|olors th|
|00006370| 61 74 20 6f 63 63 75 72 | 20 66 65 77 65 72 20 74 |at occur| fewer t|
|00006380| 68 61 6e 20 61 20 63 65 | 72 74 61 69 6e 20 6e 75 |han a ce|rtain nu|
|00006390| 6d 62 65 72 20 6f 66 20 | 74 69 6d 65 73 20 77 6f |mber of |times wo|
|000063a0| 75 6c 64 20 62 65 20 63 | 6f 6e 73 69 64 65 72 65 |uld be c|onsidere|
|000063b0| 64 20 6e 6f 69 73 65 20 | 61 6e 64 20 65 69 74 68 |d noise |and eith|
|000063c0| 65 72 20 74 68 72 6f 77 | 6e 20 6f 75 74 20 63 6f |er throw|n out co|
|000063d0| 6d 70 6c 65 74 65 6c 79 | 20 6f 72 20 72 65 64 75 |mpletely| or redu|
|000063e0| 63 65 64 20 62 65 66 6f | 72 65 20 6d 6f 72 65 20 |ced befo|re more |
|000063f0| 73 69 67 6e 69 66 69 63 | 61 6e 74 20 63 6f 6c 6f |signific|ant colo|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.